Binomial Coefficients Proof: $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$. 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!
 A: 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}
$$
A: Simpler to prove by induction is Vandermonde's Identity:
$$
\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}=\binom{n+m}{k}\tag{1}
$$
For $n=0$, note that the only non-zero term in the sum is when $j=0$. Therefore, the sum is
$$
\binom{m}{k}\tag{2}
$$
as $(1)$ says. Now, assume that $(1)$ holds for $n$, then compute
$$
\begin{align}
\sum_{j=0}^k\binom{n+1}{j}\binom{m}{k-j}
&=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^k\binom{n}{j-1}\binom{m}{k-j}\\
&=\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}+\sum_{j=0}^{k-1}\binom{n}{j}\binom{m}{k-1-j}\\
&=\binom{n+m}{k}+\binom{n+m}{k-1}\\
&=\binom{n+m+1}{k}\tag{3}
\end{align}
$$
Thus, $(1)$ holds for $n+1$.
Applying $(1)$ to your question yields
$$
\begin{align}
\sum_{k=0}^n\binom{n}{k}^2
&=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\\
&=\binom{2n}{n}\tag{4}
\end{align}
$$
A: Here is a proof by counting in two ways.
Consider two urns, one with $n$ red balls and another containing $n$ blue balls. The total number of ways to choose $n$ balls (irrespective of color) in all from the two urns is ${2n \choose n}$. Alternatively,  $k$  red balls can be chosen from the first urn (in ${n \choose k}$ ways) and for each such $k$-set, $n-k$ blues balls can then be picked from the other urn (in  ${n \choose n-k}$ ways). Hence, the total number of ways to pick $n$ balls such that $k$ of them are red is ${n \choose k}{n \choose n-k} = {n \choose k}{n \choose k}$. Summing over $k$, the total number of ways is $\sum_{k=0}^{n}{n \choose k}^{2}$.
A: Let's see what happens if we consider $$\begin{align*} \binom{n+1}{k}^{\!2} &= \left(\binom{n}{k-1} + \binom{n}{k}\right)^{\!2} \\ &= \binom{n}{k-1}^{\!2} + \binom{n}{k}^{\!2} + 2\binom{n}{k-1}\binom{n}{k}. \end{align*}$$  Now taking the sum from $k = 0$ to $n+1$, observing that $\binom{n}{n+1} = 0$ and $\binom{n}{-1} = 0$, we get $$\sum_{k=0}^{n+1} \binom{n+1}{k}^{\!2} = 2\sum_{k=0}^n \binom{n}{k}^{\!2} + 2\sum_{k=1}^{n} \binom{n}{k-1}\binom{n}{k}.$$  We now wish to show the second sum on the RHS is $\binom{2n}{n+1}$. But this is a special case of Vandermonde's convolution/identity $$\sum_x \binom{r}{a+x}\binom{s}{b-x} = \binom{r+s}{a+b}, \quad a, b \in \mathbb Z,$$ where $r = s = b = 1$ and $a = -1$.  The rest follows by induction from the calculations you previously established.
But here's the funny thing:  the original identity is itself a special case of Vandermonde's, with the choice $r = s = n$, $x = k$, $a = 0$, $b = n$, since $\binom{n}{n-k} = \binom{n}{k}$.  Here's another approach:  Inductive Proof for Vandermonde's Identity?
A: I know you want an induction proof to this but I can't resist giving you a combinatorial one.
The right side is the answer to the question: "In how many ways can I draw $n$ element from a $2n$ element set" - it's obviously ${2n\choose n}$
To get the right side lets divide our $2n$ set into two n-element subsets, and lets draw $k$ elements from the first one and $n-k$ elements from the second one. There are ${n\choose k}{n\choose n-k}={n\choose k}{n\choose k}={n\choose k}^2$ ways to do it. We can do it for every k from 1 up to n and the sum gives us the total numer of ways to choose n elements from a 2n set, therefore:
$$\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$$
A: Proof using binomial theorem:
By the binomial theorem we have $$(1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^k\tag{1}$$ Also, $$(1+x)^{2n}=(1+x)^n(1+x)^n=\left(\sum_{j=0}^{n}\binom{n}{k}x^j\right)\left(\sum_{l=0}^{n}\binom{n}{l}x^l\right)\tag{2}$$
Let us look at the coefficient for the term $x^n$. From $(1)$ this is $\binom{2n}{n}$, from $(2)$ we need to sum the coefficients for $x^{j+l}$ with $j+l=n$. This looks like $$\sum_{k+l=n}\binom{n}{k}\binom{n}{l}=\sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k}=\sum_{k=0}^{n}\binom{n}{k}^2$$ Therefore $$\boxed{\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2}$$
A: I prove this using a committee forming argument:

Our argument is that this expression is finding the amount of ways to choose $n$ total people from two groups of $n$ people. First, let's rewrite this expression. We first note that$$\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2$$can be rewritten as$$\binom n0\times \binom nn+\binom n1\times \binom n{n-1}+\cdots+\binom nn\times \binom n0$$because $\binom nk = \binom n{n-k}$. Now, let's see what this means. We can imagine two groups of $n$ people. $\binom n0 \cdot \binom nn$ tells us that we choose $n$ people from the two groups of $n$ because $0+n=n$. Similarly, we have $\binom n1+\binom n{n-1}$ is also choosing $n$ people from the two groups of $n$ (since $1+n-1 = n$). Clearly, all we're doing here is finding the amount of ways to choose $n$ people from two groups of $n$ people, which is our argument. This can be done in $\binom{2n}{n}$ ways. Therefore,$$\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n},$$ or simply just $$\sum_{k=0}^{n}\binom nk ^2=\binom{2n}{n}.$$
