# Proving $\sum_{i=0}^n \binom{n}{i} = 2^n$ by math induction

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 are on the right track. You finish the problem by showing that $\sum\limits_{i=0}^{k+1}\binom{k+1}{i}=2^{k+1}$. You are allowed to assume that $\sum\limits_{i=0}^{k}\binom{k}{i}=2^{k}$ is true while trying to prove the above. – TSF Apr 14 '16 at 16:22
• @TonyS.F. How do I prove the last part? That's the one I don't know how to do – user2896120 Apr 14 '16 at 16:44
• I hesitate to mention it, but one can use the Pascal Identity $\binom{k+1}{i}=\binom{k}{i}+\binom{k}{i-1}$. But a combinatorial interpretation is much the better path, and if we do that we are barely using induction. – André Nicolas Apr 14 '16 at 17:03
• From a combinatorial standpoint, what the equation $$\sum_{i = 0}^n \binom{n}{i} = 2^n$$ means is that the number of subsets of a set with $n$ elements is $2^n$. The term $\binom{n}{i}$ is the number of subsets with size $i$. – N. F. Taussig Apr 15 '16 at 9:11

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}.$$

If

$$1+4+6+4+1=2^4,$$

then by the well-known additive property of the binomial coefficients,

\begin{align}2^4+2^4=\\1+&4\ +6\ +4\ +1\ +\\ &1\ +4\ +6\ +4\ +1=\\ 1+&5+10+10+5+1=2^5.\end{align} This should be accepted as a proof by induction, as it unambiguously shows the pattern, which can be generalized for other $n$. (The first identity can also be used for the base case, but $1+1=2^1$ or $1=2^0$ are even better.)

• I downvote the silent downvoter. – Yves Daoust Apr 15 '16 at 19:16