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.

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|improve this question
11  
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
5  
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
show 4 more comments

4 Answers

up vote 15 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|improve this answer
4  
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: math.pugetsound.edu/~mspivey/CombSum.pdf –  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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.