4
$\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$
3
  • $\begingroup$ I think that they are the same. Try with small numbers to check $\endgroup$
    – Claude Leibovici
    Mar 30, 2019 at 9:31
  • $\begingroup$ How can I prove it? $\endgroup$
    – Monica
    Mar 30, 2019 at 9:34
  • $\begingroup$ Does this answer your question? Some binomial coefficient identity $\endgroup$
    – user53259
    Jul 11, 2021 at 8:57

3 Answers 3

Reset to default
3
$\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$
15
  • $\begingroup$ 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? $\endgroup$
    – user53259
    Jul 11, 2021 at 8:59
  • $\begingroup$ Please don't hesitate to edit your answer to respond to my comment, rather than starting a separate comment. $\endgroup$
    – user53259
    Jul 11, 2021 at 8:59
  • $\begingroup$ @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. $\endgroup$
    – drhab
    Jul 11, 2021 at 18:24
  • $\begingroup$ 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? $\endgroup$
    – user53259
    Jul 13, 2021 at 6:13
  • $\begingroup$ @ugro Do you agree that e.g. $\sum_{i=1}^kki=k\sum_{i=1}^ki$ where $k$ is an upper bound of summation? $\endgroup$
    – drhab
    Jul 13, 2021 at 6:33
3
$\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$
1
  • $\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, 2019 at 11:58
3
$\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 their answer.

$\endgroup$
1
  • 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, 2019 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .