Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@msh210, Thanks for your improvements. But one note: it's somewhat standard these days to denote the binomial coefficient by $\binom{n}{k}$ $\binom{n}{k}$ instead of $_n C_k$ or $C(n,k)$ or the like. So I made those changes. –  Srivatsan Dec 4 '11 at 18:59
    
@Srivatsan, I know it's standard among mathematicians, but I don't think it is in grade school, and I didn't want to include it in case the OP was unfamiliar with it. But I suppose your comment takes care of that concern. –  msh210 Dec 4 '11 at 19:00
2  
Do you know the identity $\dbinom{k+1}i=\dbinom{k}i+\dbinom{k}{i-1}$? It allows you to reduce the upper number in the binomial coefficients by $1$. You can prove it either algebraically, by manipulating $\frac{k!}{i!(k-i)!}+\frac{k!}{(i-1)!(k-i+1)!}$, or combinatorially. –  Brian M. Scott Dec 4 '11 at 19:01
    
@msh210 You raise a fair point :). In that case, it might be a good idea to make the edit anyway, and leave a comment explaining the notation. –  Srivatsan Dec 4 '11 at 19:08
1  
This looks like a duplicate of this question. –  robjohn Dec 4 '11 at 19:08
show 1 more comment

marked as duplicate by Brian M. Scott, Srivatsan, robjohn, Mitch, Sivaram Ambikasaran Dec 4 '11 at 20:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
It works, but it’s overkill (and a bit harder than necessary). –  Brian M. Scott Dec 4 '11 at 19:33
1  
I strongly disagree with the assertion that "all that matters" about a given solution to a problem is whether the solution works! –  Brad Dec 4 '11 at 19:49
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}$ –  robjohn Dec 4 '11 at 19:59
add comment

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