sum and binomial coefficient induction proof

Question

I bet the proof is simple but I have little experience with binomial coefficients and sums. I am curious about how you would solve this by induction:

$$ \sum_{i=0}^k {n\choose i} \leq n^k + 1$$

for $1 \leq k \leq n$. Where $n$ and $k$ are integers.

Answer 1

• I assume that checking for the base case is done
• Also, let's assume it's true for $k \leftarrow k$
• Now we will show that the statement is true for $k \leftarrow k+1$ $$\sum_{i=0}^{k+1} {n\choose i} = \sum_{i=0}^{k} {n\choose i} + {n\choose {k+1}}\leq n^k+1+ {n\choose {k+1}}$$ So it comes down to show that $$n^k+1+ {n\choose {k+1}} \le n^{k+1}+1$$ Or equivalently, $${n \choose k+1} \leq n^{k+1}-n^k = n^k(n-1)$$ Now using the fact that $${n \choose k+1} = \frac{n\cdot(n-1)\cdots(n-k)}{(k+1)!}$$ it's quite easy to check that $$\frac{n\cdot(n-1)\cdots(n-k)}{(k+1)!} \le n^k(n-1)$$ is true.