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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

Hint:

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

you will get the required solution.

Answer 4

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$

Answer 5

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

Answer 6

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