<s>[INST] Prove by induction that ${2n \choose n} > \frac{2^{2n-1}}{n}$ for every natural number n≥2 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.
 [/INST] 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)$.
</s>