# Formula for binomial coefficients

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!

-
I believe it's the same formula as in this question. – Martin Sleziak Jan 12 '12 at 19:11

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.

-
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