1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Patrick Da Silva Oct 18 '13 at 6:50
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – adrian smith Oct 18 '13 at 7:43
  • $\begingroup$ This happens because $\binom{n}{k}=\binom{n}{n-k}$. Then, change the index of summation from $i$ to $j=2n+1-i$. $\endgroup$ – detnvvp Oct 18 '13 at 8:13
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Hint:

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

you will get the required solution.

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

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$

$\endgroup$
0
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.