Prove by induction that for n > 8, ${n \choose k} < 2^{n-2}$ for each $k \in \mathbb{Z}$

Question

This problem also comes with a second-half that then asks again to prove by induction that for every $n > 7$, $\displaystyle {n \choose k} < (n-3)!$ for each integer $k$.

I have gotten to what I think is the base case for the first half, but I am very lost. Any help?

Answer 1

The inequality is true for $n=9$ since $max({9 \choose k})={9 \choose 4}={9 \choose 5}=126<2^{9-2}$

Now we use the following identity

${{n+1} \choose k} = {n \choose k} + {n \choose {k-1}}$

If the inequality is true for $n>8$, then

${{n+1} \choose k} = {n \choose k} + {n \choose {k-1}}<2^{n-2}+2^{n-2}=2^{n+1-2}$ or simply

${{n+1} \choose k}<2^{n+1-2}$

Therefore, the inequality is true for all $n>8$ by induction.

Answer 2

You know that the maximum value of ${n \choose k}$ is given as follows:

If n is even, $max {n\choose k} = \Large\frac {n!}{\frac {n}{2}!\frac {n}{2}!}$, or $k=\frac{n}{2}$ and $n-k=\frac{n}{2}$

If n is odd, $max {n\choose k} = \Large\frac {n!}{\frac {n-1}{2}!\frac {n+1}{2}!}$, or $k=\frac{n-1}{2}$ and $n-k=\frac{n+1}{2}$.

So in order to prove that ${n \choose k}<2^{n-2}$, it is sufficient to prove the inequality for the max values for both odd and even cases.

First we prove that n=9 holds. ${9 \choose 4}=\frac {9!}{4!5!}= 126 < 128=2^{9-2} $. So n=9 holds.

Let $n=p$ hold for some value of $p>9$

Case 1: p is even. $\therefore\Large\frac{p!}{\frac{p}{2}!\frac{p}{2}!}<2^{p-2}$

Now $\Large\frac{p+1}{\frac{p}{2}+1}<2$.

Thus we can multiply the 2 given inequalities to get $\Large\frac{p!*(p+1)}{\frac{p}{2}!\frac{p}{2}!(\frac{p}{2}+1)}<2^{p-2}*2$

Or $\Large\frac{(p+1)!}{\frac{p}{2}!(\frac{p}{2}+1)!}<2^{p-1}$. Thus it holds when p is even.

Case 2: p is odd. $\therefore\Large\frac{p!}{\frac{p-1}{2}!\frac{p+1}{2}!}<2^{p-2}$

now $\frac{p+1}{\frac{p-1}{2}+1}=2$.

We can still multiply the inequality and the equality to get $\Large\frac{p!*(p+1)}{\frac{p-1}{2}!\frac{p+1}{2}!(\frac{p-1}{2}+1)}<2^{p-2}*2$

Or $\large\frac{(p+1)!}{\frac{p+1}{2}!(\frac{p+1}{2})!}<2^{p-1}$. Thus it holds when p is odd also.

$\Rightarrow$ The given inequality is true for n>8