2
$\begingroup$

Possible Duplicate:
Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I am trying to prove $\sum \limits_{i=0}^n \binom{n}{i} = 2^n$ by induction. I've been all over the net looking for a solution because I just don't understand how to go about it. I know the binomial theorem is involved somehow. I found this site which seems to explain it pretty well but I just cant wrap my head around the method.

Can you show me the algebra for this, I don't understand how they get were they are going. How do you algebra $\binom{k+1}{\textrm{anything}}$ into $\binom{k}{\textrm{anything}}$? I just can't make sense of it.

So assume that $\sum \binom{k}{i} = 2^k$.

$\sum \binom{k+1}{i} = \binom{k+1}{0} +\binom{k+1}{1} + \cdots +\binom{k+1}{k} + \binom{k+1}{k+1} ,$ the right side should boil down to $2^{n+1}$.

I'm sure after I'm shown this I will still have questions, but I'm just hoping it will make more sense. Thank you.

  • 0
    @robjohn: It is, and both Mi$k$e Spivey’s a$n$d pic$a$$k$hu’s answers should be helpful to the OP, so I’ve voted to close.2011-12-04

1 Answers 1

2

Here is a hint to get you started. Begin with the Binomial Expansion \begin{align} (x + y)^{n} = \sum_{k = 0}^{n} \binom{n}{k} x^{k} y ^{n-k}. \end{align} Can you prove this identity by induction on $n$? If not, surely the base case $n = 1$ is easy to see and the following inductive hypothesis is not much harder to show: \begin{align} (x+y)^{n+1} = (x + y)(x + y)^{n} = \sum_{k = 0}^{n} \binom{n}{k} x^{k + 1} y ^{n-k} + \sum_{k = 0}^{n} \binom{n}{k} x^{k} y ^{n-k + 1} \end{align} Now separate the terms, shift indices, unify the sums and use Pascal's Binomial Coefficient Identity (in the comments above) to finish the inductive proof.

To recover your sought-after identity, set $x = y = 1$.

  • 2
    If we are going to bring in the binomial theorem, we might as well just apply it: $2^k=(1+1)^k=\sum\limits_{i=0}^k1^{k-i}1^i\binom{k}{i}=\sum\limits_{i=0}^k\binom{k}{i}$2011-12-04