# 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!

#### Solutions Collecting From Web of "Formula for binomial coefficients"

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.