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

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.

-

## 2 Answers

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

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

-