Prove that $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.
I am trying to prove this by induction. I am having some difficulty after the induction step.
Here is what I have so far:
I start with ${2(m+1) \choose m+1}$ and want to work my way to the summation, with m+1.
Using Pascal's law twice, ${2(m+1) \choose m+1}$= ${2m \choose m-1}$+${2m \choose m}$+${2m \choose m}$+${2m \choose m+1}$= $\sum_{k=0}^m {m \choose k} ^{2}$ +$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}$+${2m \choose m+1}$= 2[$\sum_{k=0}^m {m \choose k} ^{2}$+${2m \choose m+1}]$.
The second equality is by the induction hypothesis. I am not sure what to do about the extra factor of two and if there are any theorems about binomial coefficients that could help.
Thank you!
Best Answer
Combinatorial Proof
Consider the number of paths in the integer lattice from $(0,0)$ to $(n,n)$ using only single steps of the form: $$(i,j)→(i+1,j)$$ $$(i,j)→(i,j+1)$$
that is, either to the right or up. This process takes $2n$ steps, of which $n$ are steps to the right. Thus the total number of paths through the graph is equal to $\binom{2n}{n}$.
Now let us count the paths through the grid by first counting the paths:
$\qquad$ (1) from $(0,0)$ to $(k,n−k)$
and then the paths:
$\qquad$(2): from $(k,n−k)$ to $(n,n)$.
Note that each of these paths is of length $n$.
Since each path is $n$ steps long, every endpoint will be of the form $(k,n−k)$ for some $k\in\{1,2,\ldots,n\}$, representing $k$ steps right and $n−k$ steps up.
Note that the number of paths through $(k,n−k)$ is equal to $\binom{n}{k}$, since we are free to choose the $k$ steps right in any order. We can also count the number of n-step paths from the point $(k,n−k)$ to $(n,n)$. These paths will be composed of $n−k$ steps to the right and $k$ steps up. Therefore the number of these paths is equal to $\binom{n}{n−k}=\binom{n}{k}$.
Thus the total number of paths from $(0,0)$ to $(n,n)$ that pass through $(k,n−k)$ is equal to the product of the number of possible paths from $(0,0)$ to $(k,n−k)$ i.e. $\binom{n}{k}$, and the number of possible paths from $(k,n−k)$ to $(n,n)$ i.e $\binom{n}{k}$.
So the total number of paths through $(k,n−k)$ is equal to $\binom{n}{k}^2$.
Summing over all possible values of $k=0,\ldots,n$ gives the total number of paths.
Thus we get: $$ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n} $$