3
$\begingroup$

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?

$\endgroup$
4
  • 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$ Apr 14, 2016 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$ Apr 14, 2016 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$ Apr 14, 2016 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$ Apr 15, 2016 at 9:11

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .