prove $\sum_{i=0}^{n}\binom{2n+1}{i}=2^{2n}$

Can someone help me to prove $\sum_{i=0}^{n}\binom{2n+1}{i}=2^{2n}$.

The right side means the total number of subsets of $[1,2,3,..,2n]$. Then What does the left side mean? Can someone please help me? Thank you.

• Welcome to MSE :) Notice that the top bound of your sum is $n$, not $2n$, and the binomial coefficient has $2n+1$ in it, not $2n$! ;) so it does not exactly represent what you just said! Callus's answer explains that. – Patrick Da Silva Oct 18 '13 at 6:50

You have that $$2^{2n+1}=\sum_{i=0}^{2n+1}\binom{2n+1}{i}=\sum_{i=0}^{n}\binom{2n+1}{i}+\sum_{i=n+1}^{2n+1}\binom{2n+1}{i}=$$$$\sum_{i=0}^{n}\binom{2n+1}{i}+\sum_{i=n+1}^{2n+1}\binom{2n+1}{2n+1-i}=$$$$\sum_{i=0}^{n}\binom{2n+1}{i}+\sum_{j=0}^{n}\binom{2n+1}{j}=2\sum_{i=0}^{n}\binom{2n+1}{i}.$$ So, $\displaystyle \sum_{i=0}^{n}\binom{2n+1}{i}=2^{2n}$.

• Can you explain how did you get from $\sum_{i=n+1}^{2n+1}\binom{2n+1}{2n+1-i}$ to $\sum_{j=0}^{n}\binom{2n+1}{j}$? Thanks – adrian smith Oct 18 '13 at 7:43
• This happens because $\binom{n}{k}=\binom{n}{n-k}$. Then, change the index of summation from $i$ to $j=2n+1-i$. – detnvvp Oct 18 '13 at 8:13

Consider subsets of the set $[1,\ldots,2n,\theta]$ of size $\leq n$. Given such a subset $T$, map it to a subset of $[1,\ldots,2n]$ in the following way. If $\theta\notin T$, then $T$ itself is a subset of $[1,\ldots,2n]$, so send it to itself. If $\theta\in T$, then send $T$ to its complement. This mapping gives a bijection between subsets of $[1,\ldots,2n,\theta]$ of size $\leq n$ and subsets of $[1,\ldots,2n]$ of any size.

Hint:

Write down the binomial expantion of $(x+y)^{2n}$ and set $x = y = 1$

you will get the required solution.

• I think this will prove a different statement than what OP is asking. – Callus Oct 18 '13 at 6:35
• Well Yes, I got the question wrong, but you explained it very clearly, what he/she wanted. – Shravan40 Oct 18 '13 at 6:42

It appears that the statement you proposed is not even true. Could you verify it and edit it as necessary?

Edit: As @adrian corrected your equality, here is a Counting in Two Ways proof.

The right hand side is the number of subsets of $[2n]$.

For the left hand side, we partition on the number of elements we want into our subset. If we let $i$ element in our subset, then each summand $\binom{2n}{i}$ would be the ways to choose that many elements out of $2n$ elements, according to the definition of binomial coefficient. Then, according to the Rule of Sum, we know that |LHS|=|RHS|, thus the equality holds. $\square$

We have $$(x+y)^{2n}=\sum_{i=0}^{2n}{2n \choose i} x^i y^{2n-i}.$$ Put $x=y=1.$ Then we get $$\sum_{i=0}^{2n} {2n \choose i}=2^{2n}.$$

• This proves a different statement than what the OP asked for. – Callus Oct 18 '13 at 6:33
• yes, of cource. I hope he will correct the problem. – Leox Oct 18 '13 at 6:35
• But the statement he wrote is also correct. – Callus Oct 18 '13 at 6:37
• ooops! You are right..sorry – Leox Oct 18 '13 at 6:48

Note that the expression $\sum_{i=0}^n \binom{2n+1}{2}$ is actually the sum of all values in the $2n$ row in the Pascal's triangle, counting the first row as $0$. We know that the sum of all values in any row of Pascal's Triangle is power of $2$. Here's the proof:

First we should know how a row is generated in a Pascal's Triangle. Any number in the $n^{th}$ row will participate in two number in the $(n+1)^{th}$ row. Let's the number we ara focused on is the $k^{th}$ number in the $n^{th}$ (Note we are again starting to count from 0). So the sum of that number and the number on left of it, will generate the $k^{th}$ number in the $(n+1)^{th}$ row, while the sum of that number and the number on the right of him will generate the $(k+1)^{th}$ number in the $(n+1)^{th}$ row

Let $\sigma(n)$ denote the sum of all numbers in the $n^{th}$ row of the pascal triangle then we have:

$$\sigma(n) = a_{n0} + a_{n1} + a_{n2} +... + a_{nn}$$

We know how a number is generated in a Pascal's triangle (we mentioned that previously) so we have:

$$\sigma(n) = a_{(n-1)-1} + a_{(n-1)0} + a_{(n-1)0} + a_{(n-1)1} + a_{(n-1)1} + a_{(n-1)2} +... + a_{(n-1)(n-1)} + a_{(n-1)n}$$

$$\sigma(n) = a_{(n-1)-1} + 2(a_{(n-1)0} + a_{(n-1)1} + a_{(n-1)2} +... + a_{(n-1)(n-1)}) + a_{(n-1)n}$$

We know that $a_{(n-1)-1} = a_{(n-1)n} = 0$, so we have:

$$\sigma(n) = 2(a_{(n-1)0} + a_{(n-1)1} + a_{(n-1)2} +... + a_{(n-1)(n-1)}) = 2\sigma(n-1)$$

So going recursively back we have:

$$\sigma(n) = 2\sigma(n-1) = 2^2\sigma(n-2) = 2^3\sigma(n-3)... = 2^k\sigma(n-k)$$

So if we set $k=n$ and using the fact that the sum in the first($0^{th}$) row is $1$ we have:

$$\sigma(n) = 2^n\sigma(n-n) = 2^n$$

Because the $(2n + 1)^{th}$ is actually the $2n^{th}$ row according to our counting system for the sum we have:

$$\sum_{i=0}^n \binom{2n+1}{i} = \sigma(2n) = 2^{2n}$$

Q.E.D.

If you don't want to start counting from 0, and like to start from 1, then the formula is:

$$\sigma(n) = 2^{n-1}$$