Proving $ \binom n 0 ^2 + \binom n 1 ^2 + \dots + \binom n n ^2 = \binom { 2n} n $ without induction I have to prove that:
$$ \binom n 0 ^2  + \binom n 1 ^2  + \dots + \binom n n ^2 = \binom { 2n} n $$
I don't want a complete solution, but only a hint.
 A: The secret is to expand $(1+x)^{2n}$ in two ways:
$$
\sum_{k=0}^{2n}\binom{2n}{k}x^k=(1+x)^{2n}=\left(\sum_{k=0}^{n}\binom{n}{k}x^k\right)\left(
\sum_{k=0}^{n}\binom{n}{k}x^{n-k}\right).
$$
In the left sum the coefficient of $x^n$ is $\binom{2n}{n}$ while the the right one in
$$
\sum_{k=0}^n\binom{n}{k}\binom{n}{k}=\sum_{k=0}^n\binom{n}{k}^2.
$$
Hence
$$
\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}^2
$$
Generalization. Similiarly one can obtain that $\,\,\,\displaystyle
\binom{mn}{n}=\sum_{k_1+\cdots+k_m=n}\binom{n}{k_1}\cdots\binom{n}{k_m}.
$
A: A combinatorial proof:
Suppose you have $2n$ elements, and you want to choose $n$ among them.
Of course you can do that in $\binom {2n}{n}$ ways.
Let's count them in another way: 
consider the first half of the elements and the second half separately.
To choose $n$ elements overall, you can choose $k$ from the first half and $n-k$ from the second half, and then sum for all $k = 0 .... n$
That is $$\sum_{k=0}^n \binom nk \binom n{n-k} = \binom{2n}n$$
But of course $$ \binom nk \binom n{n-k} = \binom nk ^ 2$$ hence you are done.
A: HINT : 
Consider the coefficient of $x^n$ in the both sides of 
$$(1+x)^n(\color{red}{x+1})^n=(1+x)^{2n}.$$
A: *

*Combinatorial proof: Let $S=\{1,2...2n\}=S_{1}\cup S_{2}=\{1,2...n\}\cup\{n+1...2n\}$. Any $X \subseteq S$, $|X|=n$ from ${2n\choose n}$ possibles is a union $X=X_{1}\cup X_{2}=(X\cap S_{1})\cup(X\cap S_{2})$. If $|X_{1}=k|$, then $|X_{2}|=n-k$. So, for a fixed $k$, a pair  $[X_{1},X_{2}]$ is one from ${n\choose k} {n\choose n-k}={n\choose k}^2$. Sum by $k$ give $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$

