2
$\begingroup$

Prove, by algebraic manipulation, that:

\[ {{2n} \choose {n}} + {{2n} \choose {n+1}}={1\over2} {{2n+2} \choose {n+1}} \]

  • 0
    There's a button called "Edit" @Ethan2012-12-11

3 Answers 3

2

$\binom{2n}{n}+\binom{2n}{n+1}=\frac{(2n)!}{(n!)^2}+\frac{(2n)!}{(n+1)!(n-1)!}=\frac{(2n)!}{((n-1)!)^2}\left(\frac{1}{n^2}+\frac{1}{n(n+1)}\right)=$

$=\frac{(2n)!}{((n-1)!)^2}\frac{2n+1}{n^2(n+1)}=\frac{(2n+1)!}{n!(n+1)!}$

Try to complete the few steps left now...

1

$\binom m r+\binom m{r+1}=\frac{m!}{(m-r)! r!}+\frac{m!}{(m-r-1)! (r+1)!}=\frac{r+1}{m+1}\frac{(m+1)!}{\{(m+1)-(r+1)\}! (r+1)!}+\frac{m-r}{m+1}\frac{(m+1)!}{\{m-(r+1)\}! (r+1)!}$ $=\binom{m+1}{r+1}\cdot\left(\frac{r+1}{m+1}+\frac{m-r}{m+1}\right)=\binom{m+1}{r+1}$

Putting $m=2n,r=n,$

$\binom {2n} n+\binom {2n}{n+1}=\binom{2n+1}{n+1}=\frac{(2n+1)!}{n!(n+1)!}=\frac1 2 \frac{(2n+2)\cdot (2n+1)!}{(n+1)\cdot n!(n+1)!}=\frac1 2\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac1 2\binom{2n+2}{n+1}$

1

A general method for such identities, similar to what DonAntonio wrote but requiring less thought, is to write the binomial coefficients as fractions of factorials and clear all the denominators. (In the case at hand you'll multiply by $2((n+1)!)^2$.) Then cancel the biggest common factors you can find. What's left should be fairly easy to compute.

For this particular problem, though, a nicer-looking (but perhaps harder to find) alternative is essentially what Ethan suggested in a comment. Multiply both sides of the proposed equation by 2. (If you get the impression that I really don't like fractions, you're right.) On the left, use the fact that $C(2n,n+1)=C(2n,n-1)$ to replace one of the two $C(2n,n+1)$'s. That will set you up for three applications of Pascal's identity, which convert the left side to the right.