2
$\begingroup$

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!

  • 2
    I believe it's the same formula as in [this question](http://math.stackexchange.com/questions/73015/proof-of-sum-0-le-k-le-t-t-k-choose-rk-choose-s-t1-choose-rs1).2012-01-12

2 Answers 2

4

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.

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.

  • 0
    Mike and Byron - I am jealous. It's ironic that I wrote $2.18 above, and no-one corrected me. :)2012-01-13
0

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = i}^{m - n + i}{k \choose i}{m - k \choose n - i} & = \sum_{k = 0}^{\infty}{k + i \choose i}{m - k - i \choose n - i} = \sum_{k = 0}^{\infty}{k + i \choose k}{m - k - i \choose m - k - n} \\[5mm] & = \sum_{k = 0}^{\infty}\bracks{{-i - 1 \choose k}\pars{-1}^{k}} \bracks{{i - n - 1\choose m - k - n}\pars{-1}^{m - k - n}} \\[5mm] & = \pars{-1}^{m - n}\sum_{k = 0}^{\infty}{-i - 1 \choose k} \bracks{z^{m - k - n}}\pars{1 + z}^{i - n - 1} \\[5mm] & = \pars{-1}^{m - n}\bracks{z^{m - n}}\pars{1 + z}^{i - n - 1}\sum_{k = 0}^{\infty}{-i - 1 \choose k}z^{k} \\[5mm] & = \pars{-1}^{m - n}\bracks{z^{m - n}}\pars{1 + z}^{i - n - 1}\, \pars{1 + z}^{-i - 1} = \pars{-1}^{m - n}\bracks{z^{m - n}}\pars{1 + z}^{-n - 2} \\[5mm] & = \pars{-1}^{m - n}{-n - 2 \choose m - n} = \pars{-1}^{m - n}\bracks{{m + 1 \choose m - n}\pars{-1}^{m - n}} = \bbx{m + 1 \choose n + 1} \end{align}