4
$\begingroup$

I came across this equation when solving another combinatorics problem. I needed to prove the following identity:

$$ \begin{aligned} \binom{n+1}{k+1}&=\sum_{i=m}^{n+m-k}{\binom{n-i}{k-m}\binom{i}{m}} \end{aligned} $$

My attempt:

The right hand side is selecting $k-m$ balls from a number of red balls and $m$ balls from a number of blue balls where the number of red and blue balls vary but the total is always $n$.

I imagine this is the same as lining up $n+1$ non - colored balls, then selecting $k+1$ balls from these. Then proceed to color all balls on the left side of the $(m+1)$th selected balls blue and on the right side of it red. Thus proving the equality.

My question is, does this equality or identity have a name? For research purposes.

$\endgroup$
  • $\begingroup$ I’m not aware of any name for it, but it is a special case of (5.25) in Table $169$ of Graham, Knuth, & Patashnik, Concrete Mathematics. $\endgroup$ – Brian M. Scott Apr 13 at 5:02
  • 1
    $\begingroup$ I would call it: "Vandermonde playing hockey". $\endgroup$ – Phicar Apr 13 at 21:45

Your Answer

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

Browse other questions tagged or ask your own question.