# Thread: inductive proof that the sum (r=0:n) of (n C r)^2 = (2n C n)

1. ## inductive proof that the sum (r=0:n) of (n C r)^2 = (2n C n)

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.

2. Wikipedia describes how to prove the original equality, which is formula (8), using Vandermonde's identity:
$\displaystyle \displaystyle{m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k}\hspace{20em}(*)$
I am not sure if your line of thought can be successfully continued, but it often happens in proofs by induction that one has to generalize the induction hypothesis P(n), and Vandermonde's identity seems to be precisely this generalization.

Wikipedia gives an algebraic and a combinatorial proofs of Vandermonde's identity, but it can also be proved by induction. If we denote (*) above by $\displaystyle P(m,n,r)$, then we can to prove $\displaystyle \forall m\forall n\forall r\,P(m,n,r)$ by induction on $\displaystyle n$. Here, it is important to choose the induction hypothesis correctly. One option in proving $\displaystyle \forall m\forall n\forall r\,P(m,n,r)$ is to fix arbitrary $\displaystyle m$ and $\displaystyle r$ and then use induction, i.e., to prove $\displaystyle P(m,0,r)$ and $\displaystyle \forall n\,P(m,n,r)\to P(m,n+1,r)$. However, according to my calculations, proving $\displaystyle P(m,n+1,r)$ requires the induction hypothesis $\displaystyle P(m,n,r')$ for a different $\displaystyle r'$, namely, $\displaystyle r'=r-1$. Therefore, one should fix only $\displaystyle m$ and then prove $\displaystyle \forall r\,P(m,0,r)$ and $\displaystyle \forall n\,[(\forall r\,P(m,n,r))\to (\forall r\,P(m,n+1,r))]$. This way one gets a stronger induction hypothesis that works for all $\displaystyle r$.

It is also possible to not fix $\displaystyle m$ and use induction hypothesis $\displaystyle \forall m\forall r\,P(m,n,r)$. In general, it is safer to import the universal quantifiers into the IH rather than fixing them before the induction starts.