# 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 Mar 30, 2019 at 9:31
• How can I prove it? Mar 30, 2019 at 9:34
– user53259
Jul 11, 2021 at 8:57

$$\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.

• 1. How did you extract the $\color{limegreen}{\binom{n}{k}}$ out of the Capital-Sigma Notation? 2. Isn't $\color{red}{k}$ a Bound Variable, because $\color{red}{k}$ appears in the second combinatorial coefficient? I thought that you can't extract Bound Variables outside the summation?
– user53259
Jul 11, 2021 at 8:59
• Please don't hesitate to edit your answer to respond to my comment, rather than starting a separate comment.
– user53259
Jul 11, 2021 at 8:59
• @ugro The variables $n$ and $k$ are fixed. Only $m$ serves as index (hence is bound). Factor $\binom{n}{k}$ does not depend on $m$, so can be placed outside the summation sign. Jul 11, 2021 at 18:24
• Thanks for responding. I see that $\dbinom{n}{k}$ doesn't depend on $m$. But why are Bounds of Summation free variables? Why can $\dbinom{n}{k}$ be moved outside the summation, when $k$ is the upper bound of summation?
– user53259
Jul 13, 2021 at 6:13
• @ugro Do you agree that e.g. $\sum_{i=1}^kki=k\sum_{i=1}^ki$ where $k$ is an upper bound of summation? Jul 13, 2021 at 6:33

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 Mar 30, 2019 at 11:58

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 their answer.

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