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

Is there a simple proof for this equality:

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

thanks and sorry I forgot the basics

• Always google search and wiki search. Induction proof at proofwiki.org/wiki/Sum_of_Binomial_Coefficients_for_Given_n Commented May 12, 2012 at 16:15
• MSE ought to incorporate some AI techniques to catch duplicate questions automatically. Commented May 12, 2012 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
Commented May 12, 2012 at 16:31

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

• This is beautiful.
– 000
Commented May 12, 2012 at 18:53
• Straight out of the book. Commented May 28, 2022 at 2:47

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.

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.

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.

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.