<s>[INST] Prove by induction that for n > 8, ${n \choose k} < 2^{n-2}$ for each $k \in \mathbb{Z}$ 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?
 [/INST] 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
</s>