here's the specific problem I have:

I need to show that

$\displaystyle \displaystyle\sum\limits_{r=0}^{n}{{n}\choose{r+1} }{{n}\choose{r}}={{2n}\choose{n+1}}$

Here's how I got there:

Here's the original problem, I need to prove:

$\displaystyle \displaystyle\sum\limits_{r=0}^k{{k}\choose{r}}^2 = {{2k}\choose{k}}$

by induction.

I started by testing the base step and assuming that it's true for some k=n. then I set k=n+1, then expanded the sum and used Pascal's identity to get

$\displaystyle \sum_{r=0}^{n+1}{{n+1}\choose{r}}^2 = [{{n}\choose{0}}+{{n}\choose{-1}}]^2+[{{n}\choose{1}}+{{n}\choose{0}}]^2+[{{n}\choose{2}}+{{n}\choose{1}}]^2+...+[{{n}\choose{n}}+{{n}\choose{n-1}}]^2+[{{n}\choose{n+1}}+{{n}\choose{n}}]^2$

I distributed everything (and crossed out the terms that were 0), and got an unholy mess:

$\displaystyle =[{{n}\choose{0}}^2]+

[{{n}\choose{1}}^2+2{{n}\choose{1}}{{n}\choose{0}}+ {{n}\choose{0}}^2]+

[{{n}\choose{2}}^2+2{{n}\choose{2}}{{n}\choose{1}}+ {{n}\choose{1}}^2]+

...

+[{{n}\choose{n}}^2+2{{n}\choose{n}}{{n}\choose{n-1}}+{{n}\choose{n-1}}^2]+[{{n}\choose{n}}^2]$

I noticed that if I reordered the sum so that the first terms in each bracket were grouped together, the last terms in each bracket were grouped together, and the middle terms were grouped, I would have:

$\displaystyle

\displaystyle\sum\limits_{r=0}^{n+1}{{n+1}\choose{ r}}^2 =

\displaystyle\sum\limits_{r=0}^{n}2{{n}\choose{r}} ^2+

\displaystyle\sum\limits_{r=0}^{n}2{{n}\choose{r+1 }}{{n}\choose{r}}$

by my inductive hypothesis, the first summation works out to $\displaystyle 2{{2n}\choose{n}}$. If I expand out $\displaystyle {{2n+2}\choose{n+1}}$, I get $\displaystyle 2{{2n}\choose{n}}+2{{2n}\choose{n+1}}$.

If I can show that $\displaystyle \sum_{r=0}^{n}{{n}\choose{r+1}}{{n}\choose{r}}={{2 n}\choose{n+1}}$, then I'll be done.

I'm currently trying to work it out through another proof by induction, but I get the feeling it will lead me nowhere. Any help would be appreciated. Especially help in the form of telling me that I'm making it far more complicated than I need to.

Also, the book says that the original problem is Lagrange's Identity, but I wasn't able to draw any obvious parallels between Lagrange's Identity and the original problem.