Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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.

@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
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
This looks like a duplicate of this question. – robjohn Dec 4 '11 at 19:08
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|cite|improve this answer
It works, but it’s overkill (and a bit harder than necessary). – Brian M. Scott Dec 4 '11 at 19:33
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
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

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