1
$\begingroup$

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

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

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.

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

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

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.