Proving that $\binom{2n}{n} > n2^n , \forall n \ge 4 $

Question

I'm trying to prove the following statement: $\binom{2n}{n} > n2^n , \forall n \ge 4 $

This is my attempt at an inductive proof:

Let $P(n)$ be the following proposition: "$\binom{2n}{n} > n2^n , \forall n \ge 4 $"

Base case:

$\binom{2*4}{4} = 70 > 4*2^4 = 64$ so $P(4)$ is true.

Inductive step:

(I assume as an inductive hypothesis that P(n) is true and try to show that P(n+1) is true)

$\binom{2(n+1)}{n+1} = \binom{2n+2}{n+1} = \binom{2n+1}{n+1} + \binom{2n+1}{n}$

$= \binom{2n}{n} + \binom{2n}{n+1} + \binom{2n}{n} + \binom{2n}{n-1}$

$= 2 \binom{2n}{n} + \binom{2n}{n+1} + \binom{2n}{n-1}$

$= 2 \binom{2n}{n} + \frac{(2n)!}{(n+1)!(2n-(n+1))!} + \frac{(2n)!}{(n-1)!(2n-(n-1))!}$

$= 2 \binom{2n}{n} +2 \frac{(2n)!}{(n+1)!(n-1)!} $

By the inductive hypothesis we have:

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

And here I'm stuck. If I could prove that $\frac{(2n)!}{(n+1)!(n-1)!} \ge 2^n , \forall n \ge 4 $ the last step would show that P(n+1) is true. But I haven't been able to prove that. Can anyone help me ?

Answer 1

$$\frac{(2n)!}{(n+1)!(n-1)!} =\frac n{n+1}\cdot{2n\choose n}\ge \frac{n^2}{n+1}2^n$$

---

A more direct proof for a better claim: $2n\choose n$ is the largest of $2n+1$ summands in the expansion of $(1+1)^{2n}$, hence $$ {2n\choose n}\ge\frac1{2n+1}\cdot 4^n.$$

Answer 2

You can actually do this without explicit induction.

$$\binom{2n}{n} = \frac{(2n)(2n-1)\dots(2n-(n-1))}{n(n-1)\dots2 \cdot 1} = \frac{2n}{n} \cdot \frac{2n-1}{n-1} \cdot \dots \cdot \frac{n+2}{2} \cdot \frac{n+1}{1}$$

Each of those $n$ fractions is bigger than or equal to $2$, thereby providing our $2^n$; but we can do better by noting that in fact the final two fractions come to $\frac{1}{2} (n+2)(n+1)$ which is bigger than $4n$, not just bigger than $4$, when $n > 4.56$. We could just leave it there after verifying the $n=4$ case manually, or we can do even better by accounting for the final three fractions, whereupon we have that $\frac{1}{6} (n+1)(n+2)(n+3) > 8n$ when $n > 3.66$.

So as long as there are at least a final three fractions (i.e. $n \geq 3$), and as long as $n > 3.66$, the result holds, and in fact it holds pretty massively.