Erdos remarked somewhere the bound
$$
{{2n}\choose{n}}<\frac{4^n}{\sqrt{2n+1}}.
$$
This can be established by induction:
$$
{{2n+2}\choose{n+1}}=\frac{(2n+1)(2n+2)}{(n+1)(n+1)}{{2n}\choose{n}}
$$
and if we have the bound for $n$, we only have to show
$$
\frac{2(2n+1)}{(n+1)\sqrt{2n+1}}<\frac{4}{\sqrt{2n+3}}
$$
which reduces to $4n^2+8n+3<4n^2+8n+4$.
Péter Komjáth
- 7.1k
- 2
- 37
- 43