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

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a series of algebraic manipulations that can lead from $\sum\limits_{i=0}^n \binom{n}{i}$ to $2^n$.

share|cite|improve this question
is the proof you looking for using $(1+1)^n=2^n$? – Arjang Jan 24 '11 at 4:30
Well, no. That one I was also aware of. It's more of a curiosity if there's any direct method to go from the summation to $2^n$. – JSchlather Jan 24 '11 at 4:40
One should not think of the algebraic and combinatorial proofs as different. There is a straightforward dictionary between algebra and combinatorics in these cases (and it is given by taking generating functions). – Qiaochu Yuan Jan 24 '11 at 9:12
Zeilberger's algorithm might do it - it's a useful tool for this kind of problem in general (sum from $-\infty$ to $\infty$ of a hypergeometric with finite support). – Peter Taylor Jan 24 '11 at 9:29
@Peter Taylor: Zeilberger's algorithm produces the recurrence given in my answer. See Section 5.8 of Concrete Mathematics. – Mike Spivey Jan 24 '11 at 14:15
up vote 17 down vote accepted

Here's one. Let $g(n) = \sum \limits_{i=0}^n \binom{n}{i}$. Then

$$g(n+1) - g(n) = \sum_{i=0}^{n+1} \binom{n+1}{i} - \sum_{i=0}^n \binom{n}{i} = \sum_{i=0}^{n+1} \left(\binom{n+1}{i} - \binom{n}{i}\right) = \sum_{i=0}^{n+1} \binom{n}{i-1} $$ $$= \sum_{i=0}^n \binom{n}{i} = g(n).$$ Here, we use the fact that $\binom{n}{n+1} = \binom{n}{-1} = 0$, as well as the binomial recurrence $\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$.

Thus we have $g(n+1) = 2g(n)$, with $g(0) = 1$. Since $g(n)$ doubles each time $n$ is incremented by 1, we must have $$g(n) = \sum_{i=0}^n \binom{n}{i} = 2^n.$$

share|cite|improve this answer
This is more or less the same proof one would do to show that $(a+b)^n$ is what it is... – Mariano Suárez-Alvarez Jan 24 '11 at 5:40
@Mariano: Good observation. In fact, see the proof of Identity 1 in this paper: – Mike Spivey Jan 24 '11 at 5:57
Very nice and this proof seems to be analogous to what picakhu did as well. – JSchlather Jan 24 '11 at 5:57

Simply use the binomial formula.

$$(a + b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n - k}$$

With $a = b = 1$ you have your result.

share|cite|improve this answer

Well, here is one.

$$\sum_{i=0}^n \binom{n}{i}=2^n$$ $$\sum_{i=0}^n \binom{n}{i}+\sum_{i=0}^n \binom{n}{i}=2^{n+1}$$ $$\binom{n}{0}+\left [ \binom{n}{0}+\binom{n}{1} \right ]+...+\left [ \binom{n}{n-1}+\binom{n}{n}\right ]+\binom{n}{n}=2^{n+1}$$ $$\sum_{i=0}^{n+1} \binom{n+1}{i}=2^{n+1}$$

share|cite|improve this answer
So you're using induction? And I assume that in your last step it should be $\sum_{i=0}^{n+1}\binom{n+1}{i}$? – JSchlather Jan 24 '11 at 4:41
Yup, sorry about that. – picakhu Jan 24 '11 at 4:43

You could use exponential generating functions to prove this identity. $$\begin{eqnarray}\sum_{n\ge0}2^n\frac{x^n}{n!}&=&\sum_{n\ge0}\frac{(2x)^n}{n!}\\&=&e^{2x}\\&=&e^xe^x\\&=&\sum_{i\ge0}\frac{x^i}{i!}\sum_{j\ge0}\frac{x^j}{j!}\\&=&\sum_{n\ge0}\sum_{i=0}^{n}\frac{x^i}{i!}\frac{x^{n-i}}{(n-i)!}\\&=&\sum_{n\ge0}\sum_{i=0}^n\binom{n}{i}\frac{x^n}{n!}\end{eqnarray} $$ Now, comparing the coefficients of $x^n$ for ${n\ge0}$ gives the identity.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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