Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Which is the easiest way to prove $\sum \limits_{r=1}^n \binom{2n+1}{r} = 4^n-1$?

I encountered this problem while solving this question:

A student is allowed to select at most $n$ books from a collection of $(2n+1)$ books. If the total number of books he can select is $63$, then what is the value of $n$?

Evidently this boils to solving for $n$ in $\sum \limits_{r=1}^n \binom{2n+1}{r} = 63$, I used Mathematica to derive that close form. I am wondering how could we get that without electronic aid? I would appreciate an algebraic or combinatorial approach.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

$$ \binom{2n+1}{r}= \binom{2n+1}{2n+1-r} $$

Thus

$$\sum \limits_{r=1}^n \binom{2n+1}{r}=\sum \limits_{r=1}^n \binom{2n+1}{2n+1-r}=\sum \limits_{s=n+1}^{2n} \binom{2n+1}{s}$$

Hence

$$2\sum \limits_{r=1}^n \binom{2n+1}{r}=\sum \limits_{r=1}^n \binom{2n+1}{r}+\sum \limits_{r=n+1}^{2n} \binom{2n+1}{r}=\sum \limits_{r=0}^{2n+1} \binom{2n+1}{r}-2=2^{2n+1}-2$$

share|improve this answer
    
Thanks for you answer, but I am not getting the following two steps, $$ (1) \quad \binom{2n+1}{2n+1-r}=\sum \limits_{s=n+1}^{2n} \binom{2n+1}{s} $$ and $$ (2) \quad \binom{2n+1}{r}+\sum \limits_{r=n+1}^{2n} \binom{2n+1}{r}=\sum \limits_{r=0}^{2n+1} \binom{2n+1}{r}-2 $$ –  Quixotic Mar 16 '12 at 2:54
    
(1) I denoted by $s:= 2n+1-r$. Then $s$ runs from $n+1$ when $r=n$ to $2n$ when $r=1$. –  N. S. Mar 16 '12 at 3:12
    
(2) The sum on the left contains all the terms from $r=1$ to $r=2n$. I added the term for $r=0$ and the term for $r=2n+1$, and subtracted them. Note that $\binom{2n+1}{0}=\binom{2n+1}{2n+1}=1$. –  N. S. Mar 16 '12 at 3:14

A counting argument, which is basically a rephrasing of the algebraic approach.

Consider a subset of $\{1,2, \dots, 2n+1\}$ which has no more than $n$ elements.

This can be mapped in a 1-1 fashion to a set which has at least $n+1$ elements, by taking the complement.

Thus the total number of sets with no more than $n$ elements is half the total number of sets which comes to $\dfrac{2^{2n+1}}{2} = 4^n$.

Since you are not including the empty set, the total you are looking for is $4^n - 1$.

For a counting argument to count the total number of subsets:

You have $2$ choices for each element, either include it in the set of not. So total number is $2^{2n+1}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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