Induction for binomial coefficients I would like some help to prove the following equality :
$$\sum_{i=0}^n \binom{n}i^2=\binom{2n}n$$
I wanted to do a proof by induction :
$$\sum_{i=0}^{n+1} \binom{n+1}i^2=1+\sum_{i=1}^{n+1} \binom{n+1}i^2=1 + \sum_{i=0}^{n} \binom{n+1}{i+1}^2=1+\sum_{i=0}^{n} \bigg(\binom{n+1}i+\binom{n}{i+1}\bigg)^2$$
$$\sum_{i=0}^{n+1} \binom{n+1}i^2=1+\sum_{i=0}^{n} \bigg(\binom{n}i^2+2\binom{n}i\binom{n}{i+1}+\binom{n}{i+1}^2\bigg)=1+\binom{2n}n+ \sum_{i=0}^{n} 2\binom{n}i\binom{n}{i+1} +(\sum_{i=0}^n \binom{n}i^2-1) $$
$$\sum_{i=0}^{n+1} \binom{n+1}i^2=2\binom{2n}n+\sum_{i=0}^{n} 2\binom{n}i\binom{n}{i+1}=2\bigg(\sum_{i=0}^n \binom{n}i^2(1+\frac{n-i}{i+1})\bigg)=2(n+1)\bigg(\sum_{i=0}^n \binom{n}i^2\frac{1}{i+1}\bigg)$$
But now I'm stuck.
 A: One way to proceed is to prove a more general identity by induction, and then deduce the identity in the problem statement as a corollary.
The more general identity is called "Vandermonde's Identity":
$$\sum_{i=0}^k \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k} \tag{1}$$
for non-negative integers $k$, $m$ and $n$.  We give a proof by induction over $n$. The case $n=0$ reduces to $\binom{m}{k} = \binom{m}{k}$.  Now suppose $(1)$ holds for some $n \ge 0$.  Then the $n+1$ case is
$$\begin{align}
\sum_{i=0}^k \binom{m}{i} \binom{n+1}{k-i} &= \sum_{i=0}^k \binom{m}{i} \left( \binom{n}{k-i-1} + \binom{n}{k-i} \right)  \tag{2}\\
&=\sum_{i=0}^k \binom{m}{i}  \binom{n}{k-i-1} + \sum_{i=0}^k \binom{m}{i}  \binom{n}{k-i} \\
&=\binom{m+n}{k-1} + \binom{m+n}{k} \tag{3} \\
&= \binom{m+n+1}{k} \tag{4}
\end{align}$$
This completes the proof by induction.  At steps $(2)$ and $(4)$ we used the identity
$$\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$$ and at step $(3)$ we used the inductive hypothesis.
To prove $$\sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}$$
from $(1)$, take the special case $k=n$, $m=n$, and apply the identity
$$\binom{n}{i} = \binom{n}{n-i}$$
A: The binomial theorem says $$(1+x)^n=\sum^n_{i=0}\binom{n}{i}x^i,$$ and we know that
$$(1+x)^n(1+x)^n=(1+x)^{2n}.$$ Comparing the coefficient of $x^n$, we get $$\sum^n_{i=0}\binom{n}{i}\binom{n}{n-i}=\sum^n_{i=0}\binom{n}{i}^2$$ on the LHS, and $\binom{2n}{n}$ on the RHS.
