Prove by induction that ${2n \choose n} > \frac{2^{2n-1}}{n}$ for every natural number n≥2

Question

When I plug n+1 and elaborate on that I end up with half a sheet of paper full of numbers but I can't get to anything conclusive on the right side. Any help would be appreciated.

Answer 1

Write

$$ \binom{2(n+1)}{n+1} = \frac{(2n)! \cdot (2n+1)(2n+2)}{(n+1)!(n+1)!} \\= \frac{(2n)!(2n+1)(2n+2)}{(n!)^2(n+1)^2} > \frac{2^{2n-1}}{n} \frac{(2n+1)(2n+2)}{(n+1)^2} = \frac{2^{2n-1}}{n+1} \frac{2(n+1/2)}{n} \frac{2(n+1)}{n+1} $$

where we identified $\frac{(2n)!}{(n!)^2} = \binom{2n}{n}$ to make use of inductive hypothesis, and in the last equality we have

$$ n + 1/2 > n, \Rightarrow \frac{2(n + 1/2)}{n} > 2, \; \frac{2(n+1)}{n+1} = 2 $$

so the final product is equal to $\frac{2^{2n-1}}{n+1} \cdot 2^{2} = \frac{2^{2n+1}}{n+1} = \frac{2^{2(n+1)-1}}{n+1}$, as required.

In the proof above, we've made use of the fact that $(n+1)! = n! (n+1)$.

Answer 2

$${2(n+1) \choose n+1}={2n \choose n}\frac {(2n+2)(2n+1)}{(n+1)^2}={2n \choose n}\frac {4n+2}{n+1}\\ \frac{2^{2(n+1)-1}}{n+1}=\frac {4\cdot 2^{2n-1}}{n+1}=\frac {2^{2n-1}}n\cdot\frac {4n}{n+1}$$ So assuming the statement is true for $n$ we have $${2(n+1) \choose n+1}={2n \choose n}\frac {4n+2}{n+1}\gt{2n \choose n}\frac {4n}{n+1}\gt\frac {2^{2n-1}}n\cdot\frac {4n}{n+1}=\frac{2^{2(n+1)-1}}{n+1}$$ and we have proven it for $n+1$

Answer 3

For all $k\ge 1,$ $$\frac{\binom{2k}k}{\binom{2(k-1)}{k-1}}=\frac{2k(2k-1)}{k\cdot k} > 4\cdot \frac{k-1}{k}$$ Therefore, letting $c_k=\binom{2k}k$, and noting the telescoping product below, $$ c_n=\frac{c_{n}}{c_{n-1}}\cdot \frac{c_{n-1}}{c_{n-2}}\cdots\cdot\frac{c_2}{c_1}\cdot c_1\ge 4\cdot \frac{n-1}{n}\cdot4\cdot\frac{n-2}{n-1}\cdots4\cdot\frac{1}{2}\cdot 2=\frac1n 2^{2n-1} $$