$\displaystyle \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:
$\displaystyle \sum_{r=0}^{n}\binom{n}{r}^{2}$
become?
$\displaystyle \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:
$\displaystyle \sum_{r=0}^{n}\binom{n}{r}^{2}$
become?
It will help if you think of it this way.
$\displaystyle \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
$\displaystyle \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
$\displaystyle \binom{3}{0}$ ways, but this forces me to put all 3 in the last 3 spots and I can do this in
$\displaystyle \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
$\displaystyle \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
$\displaystyle \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
$\displaystyle \binom{3}{3},\text{ and } \binom{3}{0}$ ways respectively
So the total number of ways to do this is
$\displaystyle \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
$\displaystyle \binom{n}{k}=\binom{n}{n-k}$ using this we get
$\displaystyle \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.
Here is one way to see it.
We have $\displaystyle (1+x)^n=\sum_{j=0}^n{n \choose j}x^j$. We can write this backwards as $\displaystyle (1+x)^n=\sum_{j=0}^n{n \choose n-j}x^{n-j}$. If you multiply both equalities, you have
$\displaystyle (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 $\displaystyle x^n$ in the left-hand side is $\displaystyle {2n \choose n}$, and the coefficient of $\displaystyle x^n$ in the right-hand side is seen to be equal to $\displaystyle \sum_{j=0}^n{n \choose j}{n \choose n-j}=\sum_{j=0}^n{n \choose j}^2$.