# Math Help - binomial identities

1. ## binomial identities

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

Can somebody start me on this? I have the identities in front of me, but I just make a mess. No clue. Like what does:

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

become?

2. Originally Posted by billym
$\binom{2n}{n} = \sum_{r=0}^{n}\binom{n}{r}^{2}$

Can somebody start me on this? I have the identities in front of me, but I just make a mess. No clue. Like what does:

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

become?
It will help if you think of it this way.

$\binom{2n}{n}$ is asking how many ways can I arrange n objects in 2n spots.

So lets break this up into a two part problem. For simplicity I will use n=3 and let you generalize

So we have

$\binom{2\cdot 3}{3}=\binom{6}{3}$

So we have 3 objects and 6 six spots

_ _ _ , _ _ _

Now we ask if I put 0 ojects in the first 3 spots I can do this in
$\binom{3}{0}$ ways, but this forces me to put all 3 in the last 3 spots and I can do this in
$\binom{3}{3}$ ways

Now if I put 1 object in the first 3 spots I then have to put 2 in the last 3 I can do this in
$\binom{3}{1},\text{ and } \binom{3}{2}$ ways respectively

Next will be 2 objects in the first 3 spots and 1 in the last three with

$\binom{3}{2},\text{ and } \binom{3}{2}$ ways respectively

and finally 3 objects in the first 3 spots and none in the last three gives

$\binom{3}{3},\text{ and } \binom{3}{0}$ ways respectively

So the total number of ways to do this is

$\binom{3}{0}\binom{3}{3}+\binom{3}{1}\binom{3}{2}+ \binom{3}{2}\binom{3}{1}+\binom{3}{3}\binom{3}{0}$

Now remember that

$\binom{n}{k}=\binom{n}{n-k}$ using this we get

$\binom{3}{0}^2+\binom{3}{1}^2+\binom{3}{2}^2+\bino m{3}{3}^2=\sum_{k=0}^{3}\binom{3}{k}^2$

This is the logic you need for the general proof.

I hope this helps. Good luck.

3. Here is one way to see it.

We have $(1+x)^n=\sum_{j=0}^n{n \choose j}x^j$. We can write this backwards as $(1+x)^n=\sum_{j=0}^n{n \choose n-j}x^{n-j}$. If you multiply both equalities, you have

$(1+x)^{2n}=\left(\sum_{j=0}^n{n \choose j}x^j\right)\left(\sum_{j=0}^n{n \choose n-j}x^{n-j}\right)$.

The coefficient of $x^n$ in the left-hand side is ${2n \choose n}$, and the coefficient of $x^n$ in the right-hand side is seen to be equal to $\sum_{j=0}^n{n \choose j}{n \choose n-j}=\sum_{j=0}^n{n \choose j}^2$.