A different upper bound for the binomial coefficient

Question

I need to prove the following statement:

If $3\leq k < t$ then \begin{equation*} \binom{t}{k} < 2^{t-1}-k+1. \end{equation*}

I was given the hint to prove it by induction over $t$ with $k$ fixed, which seems very reasonable.

The base case is rather easy to see: \begin{equation*} \binom{k+1}{k} = k+1 < 2^k-k+1 \Leftrightarrow 2k < 2^k \end{equation*}

However I am struggling hard with the inductive step. My approach for now is using Pascal's identity to obtain \begin{equation} \binom{t+1}{k} = \binom{t}{k}+\binom{t}{k-1} \end{equation} At this point, I would like to apply induction to both terms, but my induction is over $t$ so I am not allowed to do that. (I tried to do double induction, but the induction over $k$ seems even harder).

In the case that $k\geq \frac{t+1}{2}$ the second term is smaller or equal than the first one, so I apply induction hypothesis \begin{equation*} \binom{t+1}{k} < 2\left(2^{t-1}-k+2\right)=2^t-2k+2 < 2^t-k+1 \end{equation*}

However, I am very confused for what to do in the remaining case $k>\frac{t+1}{2}$.

Any help or hint will be appreciated, thank you!

Answer 1

If you want to deal with the formula \begin{equation} \binom{t+1}{k} = \binom{t}{k}+\binom{t}{k-1}, \end{equation} you can deal with the following statement by induction on $t$ : for all $t\geq 4$, for all $k$ such that $3\leq k<t$, $$\binom{t}{k}\leq 2^{t-1}-k+1.$$

• Base case : $t=4,t=5$ (easy to show).
• Induction : if $4\leq k \leq t-1$ \begin{align*}\binom{t+1}{k} = \binom{t}{k}+\binom{t}{k-1}&\leq 2^{t-1}-k+1+2^{t-1}-(k-1)+1\\ &\leq 2^t-k+1, \end{align*} and if $k=3$ or $k=t$ it's trivial.

Answer 2

Hint: Notice that $$\binom{t+1}{k} = \frac{(t+1)!}{(t+1-k)!k!} = \frac{t+1}{t+1-k}\cdot \frac{t!}{(t-k)!k!} =\frac{t+1}{t+1-k}\cdot\binom{t}{k}.$$