Proving $\binom{2n}{n}\le 4^n$ for all $n$ by smallest counterexample 
Prove $$\binom{2n}{n}\le 4^n$$ for all natural numbers $n$ by smallest (minimal) counterexample.

My attempt:
First, $$\binom{2n}n = \frac{(2n)!}{(n!)^2} \le 4^n\;.$$ We know that $x\ne 0$ because $\frac{(2\cdot 0)!}{(0!)^2} = 1$ which is true. So $x\ge 2$. Now consider $x-1\in \Bbb N$. Also note that $x-1 <x$ and is the smallest counterexample. So, $n=x-1$.
$$\frac{(2(x-1))!}{((x-1)!)^2} \le 4^{x-1}$$
$$\frac{(2x-2)!}{((x-1)!)^2} \le 4^{x-1}$$
So this is where I'm stuck. Do I keep on expanding? If so, how?
 A: It does not answer the question, as it does not use an inductive argument, but it is an easier proof of the actual result
If you have $2n$ objects then the number of all the subets is $2^{2n}=4^n$.
Now $2n \choose n$ are all the subsets of $2n$ containing $n $ elements.
A: Let $n^*$ be the minimum value of $n$ for which the inequality is violated, i.e., we have
$$\dbinom{2n^*}{n^*} > 4^{n^*}$$
It is easy to check that $n^* > 0,1$.
We then have
$$\dfrac{2n^* (2n^*-1)}{n^* n^*}\dbinom{2(n^*-1)}{(n^*-1)} > 4^{n^*} \implies 4 \left(1- \dfrac1{2n^*}\right)\dbinom{2(n^*-1)}{(n^*-1)} > 4^{n^*}$$
This gives us
$$\dbinom{2(n^*-1)}{(n^*-1)} > \dfrac{4^{n^*-1}}{1-\dfrac1{2n^*}} > 4^{n^*-1}$$
This contradicts the minimality of $n^*$.
A: HINT: In order to complete your proof, you need to show that the inequality $$\frac{(2x-2)!}{((x-1)!)^2} \le 4^{x-1}\tag{1}$$ implies that $$\frac{(2x)!}{x!^2}\le 4^x\;.$$
Now $$\frac{(2x)!}{x!^2}=\frac{2x(2x-1)(2x-2)!}{x^2(x-1)!^2}=\frac{2x(2x-1)}{x^2}\cdot\frac{(2x-2)!}{(x-1)!^2}\le\frac{2x(2x-1)}{x^2}\cdot4^{x-1}$$ by virtue of the hypothesis $(1)$. You’ll be done if you can show that
$$\frac{2x(2x-1)}{x^2}\le 4\;.$$
Can you finish it now.
A: Recall the Pascal Identity $\binom{m}{k}=\binom{m-1}{k}+\binom{m-1}{k-1}$. This can be proved by a short calculation with factorials, or by a combinatorial argument. Or else if we define the binomial coefficients using the so-called Pascal Triangle, the identity is true by definition. By the way, the "Pascal" triangle was known in China centuries before Pascal. It was even known in Europe. But I digress.
Apply the Identity to $\binom{2n}{n}$, getting $\binom{2n}{n}=\binom{2n-1}{n}+\binom{2n-1}{n-1}$. Then apply it again to the two parts. We get
$$\binom{2n}{n}= \binom{2n-2}{n}+\binom{2n-2}{n-1}+\binom{2n-2}{n-1}+\binom{2n-2}{n-2}.\tag{$1$}$$
If $n$ is a minimal counterexample, then $\binom{2n-2}{n-1} \le 4^{n-1}$. There are two such terms in the right-hand side of $(1)$, plus two smaller terms, since the central binomial coefficients are maximal. It follows that the right-hand side, and hence the left, is $\lt 4\cdot 4^{n-1}=4^n$, contradicting the assumption that $n$ is a counterexample.
