Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does someone know, if the subsequent formula holds for $m \ge n \ge i \ge 1$ and if yes, can give a reference. $$\sum_{k=i}^{m-n+i}\binom{k}{i}\binom{m-k}{n-i} = \binom{m+1}{n+1}$$ Thank you very much!

share|cite|improve this question
I believe it's the same formula as in this question. – Martin Sleziak Jan 12 '12 at 19:11
up vote 4 down vote accepted

What you want is equation (5.26) on page 169 of Concrete Mathematics (2nd edition) by Ronald Graham, Donald Knuth, and Oren Patashnik.

Corrected: For integers $m,n\geq0$ and integers $\ell,q$ with $\ell+q\geq 0$ we have $$\sum_{-q\leq k\leq \ell}{q+k\choose n}{\ell-k\choose m}={\ell+q+1\choose m+n+1}.$$

Let's now substitute your variables $i\geq 0$ and $n-i\geq 0$ in the bottom to obtain $$\sum_{-q\leq k\leq \ell}{q+k\choose i}{\ell-k\choose n-i}={\ell+q+1\choose n+1}.$$

In fact, since you have assumed $i>0$, we get even more $$\sum_{i-q\leq k\leq \ell}{q+k\choose i}{\ell-k\choose n-i}={\ell+q+1\choose n+1}.$$ That's because ${q+k\choose i}=0$ when $q+k<i$.

Redefining the $k$ variable gives $$\sum_{i\leq k\leq \ell+q}{k\choose i}{\ell+q-k\choose n-i}={\ell+q+1\choose n+1}.$$

Letting $m=\ell+q$ gives $$\sum_{i\leq k\leq m}{k\choose i}{m-k\choose n-i}={m+1\choose n+1}.$$

Is this the same as your sum? Yes!

  1. If $n=i$, then this is obvious.

  2. When $n>i$, then ${m-k\choose n-i}=0$ for $k>m-n+i$ anyway.

share|cite|improve this answer
Byron, there are a couple of typos in the book for that sum. The summation should be for $-q \leq k \leq \ell$, and it's valid for integers $m,n \geq 0$ and integer $\ell + q \geq 0$. (The corrections are listed on Knuth's web site.) – Mike Spivey Jan 12 '12 at 16:30
@Mike Yikes! I should have checked that. Thanks. – Byron Schmuland Jan 12 '12 at 16:38
Knuth's books tend to have few errors; I was surprised when I discovered this one. – Mike Spivey Jan 12 '12 at 16:42
@MikeSpivey, did you claim your $2.18? – Bruno Joyal Jan 12 '12 at 22:17
@Bruno: I wasn't the first to discover it, so no. :) I do have a check from Knuth for finding an error in The Art of Computer Programming, though. – Mike Spivey Jan 12 '12 at 23:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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