I am having some trouble using math induction to prove the following problem:
$$\sum_{i=0}^n \binom{n}{i} = 2^n$$ Where n $\geq$ 0
I know the first thing with math induction is substitute the base value for n.
Which we get $$\sum_{i=0}^0 \binom{0}{0} = 2^0$$ which equals to 1 on the left hand side and 1 on the right hand side. The base case is now verified. We move on to substituting n for k (assuming k is true) like so:
$$\sum_{i=0}^k \binom{k}{i} = 2^k$$ If k is true, k + 1 should be true as well. So we must prove k + 1 now: $$\sum_{i=0}^{k+1} \binom{k+1}{i} = 2^{k+1}$$
This is the part I am having trouble on. Are all my steps correct so far? If so, how do I finish proving this problem?
You can take advantage of the recurrence relation:
$${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k},1 \leq k \leq n-1$$
$${n \choose n} = {n \choose 0} = 1, n \geq 0.$$
Then split apart the $k+1$ sum and watch the indices to make sure you include all of the terms:
$$\sum_{j=0}^{k+1} {k+1 \choose j} \\ = \sum_{j=0}^{k} {k \choose j-1} + \sum_{j=0}^{k} {k \choose j} + {k+1 \choose k+1} \\ = \left[\left(\sum_{j=0}^{k} {k \choose j}\right) - {k \choose k} \right] + \sum_{j=0}^{k} {k \choose j} + {k+1 \choose k+1} \\ =2^k - 1 + 2^k + 1 \\ = 2 \cdot 2^k \\ = 2^{k+1}.$$