1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot! What is the intuition behind choosing s=2n−1−r? Because I wasn't able to think of that at first. $\endgroup$ – Faizal Ismaeel Sep 22 '14 at 22:00
  • $\begingroup$ @Delvacode, Observe that $$s+r=2n-1$$ and compare with the identity in the first line $\endgroup$ – lab bhattacharjee Sep 23 '14 at 4:34
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Faizal Ismaeel Sep 24 '14 at 5:45

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.