# Proving $\sum_{m=0}^n\binom{n}{m}^2 \binom{m}{n-k}=\binom{n}{k}\binom{n+k}{k}$

How can I prove this? $$\sum_{m=0}^n\binom{n}{m}^2 \binom{m}{n-k}=\binom{n}{k}\binom{n+k}{k}$$

$$0\le k \le n$$ I developed the expressions, but they are not the same. I do not know if it will be my mistake or the advisor I tried to solve for the binomial, but I could not, any idea to be able to proceed

• I think that they are the same. Try with small numbers to check – Claude Leibovici Mar 30 at 9:31
• How can I prove it? – Monica Mar 30 at 9:34

Let us prove the general form of the identity given by @Richard.

$$\sum_{r=0}^\infty \binom ar \binom br \binom rc = \binom ac \binom{a+b-c}a.$$

Replacing $$\binom ar \binom rc$$ with: $$\binom ar \binom rc=\frac{a!}{r!(a-r)!}\frac{r!}{c!(r-c)!} =\frac{a!}{c!(a-c)!}\frac{(a-c)!}{(a-r)!(r-c)!}=\binom ac\binom {a-c}{a-r},$$ one obtains: $$\sum_{r=0}^\infty \binom ar \binom br \binom rc = \binom ac\sum_{r=0}^\infty \binom br \binom {a-c}{a-r} =\binom ac \binom{a+b-c}a,$$ where in the last equality the Vandermonde's identity was used.

Inserting $$a=b=n$$ and $$c=n-k$$ yields the identity of OP, as already was pointed out by @Richard.

• Didn't know this identity was named after Vandermonde, and much simpler proof than mine. 1:0 for you, @user. +1 – Richard Mar 30 at 11:58

$$\sum_{m=0}^{n}\binom{n}{m}^{2}\binom{m}{n-k}=\binom{n}{k}\sum_{m=0}^{n}\binom{n}{m}\binom{k}{n-m}=\binom{n}{k}\binom{n+k}{n}$$where the second equality rests on the vandermonde identity.

You can use the general identity $$\sum_{k\ge0}\binom ak\binom bk\binom kc=\binom ac\binom{a+b-c}a$$ Inserting $$n$$ for $$a$$ and $$b$$ and $$n-k$$ for $$c$$ yields what you wanted to prove.
The upper bound of summation can be reduced from $$\infty$$ to $$n$$ because $$\binom nk$$ is 0 for $$k\gt n$$.

EDIT: This can be proven using Vandermonde's identity. @user gives a very simple proof in his answer.

• It would be nice to give a proof of the general identity or at least a reference to it. – user Mar 30 at 10:43