Proof by induction on multiple variables

Question

I have the following term to prove by induction: $$ \sum_{i=0}^m C(n,i)\le n^m+1 $$

I know that base case for this is n = 1 and m = 0. However, I am not sure how to proceed from there.

Answer 1

It's trivial that the inequality holds for $ m=0,1 $. Now, suppose that we have shown that it's true when $ m=k \ge 1 $. Thus, $$ \sum\limits_{i=0}^{k}{\binom{n}{i}} \le n^k+1 $$ If we can prove that $ \binom{n}{k+1} \le n^{k+1}-n^{k} $, then we're done. Indeed, $$ n^{k+1}-n^{k}=\left(n-1\right)n^k \ge \left(n-1\right)\left(\sum\limits_{i=0}^{k}{\binom{n}{i}}-1\right) > \left(n-1\right)\binom{n}{k}>\binom{n}{k+1} $$ as desired. Note that the equality occurs when $ m=1 $.