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?

  • 3
    $\begingroup$ 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. $\endgroup$ – TSF Apr 14 '16 at 16:22
  • $\begingroup$ @TonyS.F. How do I prove the last part? That's the one I don't know how to do $\endgroup$ – user2896120 Apr 14 '16 at 16:44
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Apr 14 '16 at 17:03
  • $\begingroup$ 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$. $\endgroup$ – 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}.$$




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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.