5
$\begingroup$

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 2

6

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

  • 0
    (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$.2012-03-16
5

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