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

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

-

10
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

## 3 Answers

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

-

3
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
– 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.

-

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

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 8, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.925255537033081, "perplexity_flag": "middle"}