# Sum from 0 to n of $n \choose i$? [duplicate]

Possible Duplicate:
Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$
Evaluation $\sum\limits_{k=0}^n \binom{n}{k}$

Is there a simple proof for this equality:

$$\sum_0^n {n \choose i} = 2^n$$

thanks and sorry I forgot the basics

-

– Kirthi Raman May 12 '12 at 16:15
@J.M. Of course. This has been answered many times before. – Peter Tamaroff May 12 '12 at 16:22
MSE ought to incorporate some AI techniques to catch duplicate questions automatically. – Kirthi Raman May 12 '12 at 16:25
@KVRaman when you compose a question, it shows you some suggestions of (what it thinks) similar questions. But you're right. I can see some classification (machine learning) techniques applicable here. – user2468 May 12 '12 at 16:31
I don't usually answer a question that already has four answers including some very good ones, but I've posted an answer below that I think may be the simplest way of viewing the matter and is worth knowing about. – Michael Hardy May 12 '12 at 17:12

## marked as duplicate by Peter Tamaroff, J. M., J.D., anon, Martin SleziakMay 12 '12 at 17:20

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.

## 5 Answers

Recall the relation $\displaystyle{n+1\choose i}={n\choose i}+{n\choose i-1}$, valid for every $1\leqslant i\leqslant n$. Hence, $$\sum_{i=0}^{n+1}{n+1\choose i}=1+\sum_{i=1}^n\left[{n\choose i}+{n\choose i-1}\right]+1,$$ that is, $$\sum_{i=0}^{n+1}{n+1\choose i}=1+\sum_{i=1}^n{n\choose i}+\sum_{i=0}^{n-1}{n\choose i}+1=2\sum_{i=0}^n{n\choose i}.$$ The initial value $\displaystyle\sum\limits_{i=0}^0{0\choose i}=1$ completes the recursion.

-

for your efforts – ca11111 May 12 '12 at 16:28

$$(1+1)^n = \sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix}1^i 1^{n-i}.$$ But I do not know if this is as simple as you wish.

-

Thanks, added your suggestion! – Siminore May 12 '12 at 16:12
This is beautiful. – 000 May 12 '12 at 18:53

The standard combinatorial proof is that

• The LHS counts the number of ways to choose $0$, $1$, $2, \ldots ,$ or $n$ things from a total of $n$ objects.
• The RHS counts the number of ways to go through each of $n$ objects and mark them as "choose" or "don't choose".

With a little thought, these are equal.

An algebraic proof has been posted by Siminore.

-

There are many quite simple proofs.

One of them is application of well known Newton binomial theorem: $$\sum_0^n {n \choose i} = \sum_0^n {n \choose i} 1^i 1^{n-i} = (1+1)^n = 2^n.$$

One can also prove this by combinatorial argument. Observe that ${n \choose i}$ is the number of subsets of cardinality $i$ of a set of cardinality $n$. Then $\sum_0^n {n \choose i}$ is the number of all subsets of cardinality $0, 1, 2, \dots, n$ of a set of cardinality $n$. Hence the sum counts all subsets of a $n$-set. But we know that thare are $2^n$ subsets of such set.

-

Here's a variation on the theme of Didier's answer.

Each number in Pascal's triangle gets added twice to the row below it.

The first $1$ below gets added to the next row to get the $1$ at the end, and also gets added to the next row to contribute to the $9$. Then the $8$ gets added to the next row to contribute to the $9$, and also gets added to the next row to contribute to the $36$. And so on. $$\begin{array}{ccccccccccccccccccc} & 1 & & 8 & & 28 & & 56 & & 70 & & 56 & & 28 & & 7 & & 1 \\ \\ 1 & & 9 & & 36 & & 84 & & 126 & & 126 & & 84 & & 36 & & 9 & & 1 \end{array}$$

Since each number is added twice to the next row, the sum of the numbers in the next row is twice as big.

-
{"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": 26, "mathjax_display_tex": 6, "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": true, "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.9499462246894836, "perplexity_flag": "middle"}