# 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?

-

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.

-
Well then one may proceed like: Suppose that an $n$ that violates that inequality exists. In this case, the number of subsets of $S$ (say) is less than the number of subsets of $S$ containing $n$ elements, which is absurd. I know it is lame, but appears to work :) – Lord Soth Apr 9 '13 at 19:02
@BrianM.Scott My apologies I rushed, how should I proceed delete it? or flag it to be as a comment? or perphaps a community wiki? – clark Apr 9 '13 at 19:07
@BrianM.Scott I was wondering about why my "proof by contradiction" recasting of clark's answer would not work. Or would it? Would you for example give me full points if I have written it or I would have got a $0$? I am just curious. – Lord Soth Apr 9 '13 at 19:13
@LordSoth: I can’t answer, because I wouldn’t have asked the question in that form: I’d simply have asked for a proof of the result, and clark’s answer would then be just fine. I can only say that your recasting clearly violates the intent of the question, and I can easily imagine that someone who would pose the question in the first place would mark you down for that answer, possibly even to the extent of giving no credit. (I’ve known a few like that.) – Brian M. Scott Apr 9 '13 at 19:18
@BrianM.Scott Thank you; this notion of "intention of a question" is quite an interesting thing to think about in general (at least pedagogically). – Lord Soth Apr 9 '13 at 19:23

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^*$.

-

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.

-
While I agree that this proves the claim, it seems to be an induction argument. The non-existence of a "minimal counterexample" argument reads like the contrapositive of this. (Of course, they're logically equivalent!) Assuming that $x$ is the minimal counterexample, where $\binom{2x}{x} > 4^x$, you deduce that the analogous inequality actually holds with $x$ replaced by $x - 1$. – Sammy Black Apr 9 '13 at 19:12

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.

-