1

I'm stuck at proving the following.

$$ \sum_{r=0}^{n-1} \binom{2n-1}{r} = 2^{2n-2} $$

I know that I have to use the Binomial theorem like this, letting x=1,y=1 in $(x+y)^{2n-1}$

$$ \sum_{r=0}^{2n-1} \binom{2n-1}{r} = 2^{2n-1}$$

But I don't know how to continue from there.

Faizal Ismaeel
  • 645

2 Answers2

5

As $\displaystyle\binom nr=\frac{n!}{(n-r)!\cdot r!}=\binom n{n-r},$

$$S=2\sum_{r=0}^{n-1}\binom{2n-1}r=\sum_{r=0}^{n-1}\binom{2n-1}r+\sum_{r=0}^{n-1}\binom{2n-1}r$$

Setting $s=2n-1-r$ for the second summation,

$$S=\sum_{r=0}^{n-1}\binom{2n-1}r+\sum_{s=n}^{2n-1}\binom{2n-1}s=\sum_{r=0}^{2n-1}\binom{2n-1}r=(1+1)^{2n-1}$$

lab bhattacharjee
  • 274,582
2

Split the sum in your second identity in to the sum from $r=0$ to $n-1$ and the sum from $n$ to $2n-1$. Then replacing $r$ by $(2n-1) - r$ in the second one gives you the sum from $0$ to $n-1$ of $\binom{2n-1}{2n-1-r}$, then just use the property that $\binom{n}{m} = \binom{n}{n-m}$ to make it the same as the first sum. Now divide by 2.

Matt Rigby
  • 2,316
  • 12
  • 13
  • In your answer, you said "replacing $r$ by $(2n-1) - r$ in the second one gives you the sum from $0$ to $n-1$ of $\binom{2n-1}{2n-1-r}$". Don't we get a sum from $n$ to $2n-1$ in the second one when we replace $r$ by $(2n-1) - r$ instead of $0$ to $n-1$ ? Thanks! – Faizal Ismaeel Sep 24 '14 at 05:45