Alternating sum over binomial coefficients

Question

I am trying to follow a proof in a physics paper, but got stuck with the identity $$\sum_{i=0}^n(-1)^i\binom{k}{n-i}\frac{(m+i)!}{i!} = m!\binom{k-m-1}{n}.$$ I would be very grateful if you could shed light on this mystery.

Answer 1

Here we have Chu-Vandermonde's Identity in disguise.

Dividing the left hand side by $m!$ we obtain \begin{align*} \color{blue}{\sum_{i=0}^n}&\color{blue}{(-1)^i\binom{k}{n-i}\frac{(m+i)!}{i!m!}}\\ &=\sum_{i=0}^n(-1)^i\binom{k}{n-i}\binom{m+i}{i}\\ &=\sum_{i=0}^n\binom{k}{n-i}\binom{-m-1}{i}\tag{1}\\ &\,\,\color{blue}{=\binom{k-m-1}{n}}\tag{2} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (2) we apply the Chu-Vandermonde identity.

Answer 2

$\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}$

$\ds{\sum_{i = 0}^{n}\pars{-1}^{i}{k \choose n - i}{\pars{m + i}! \over i!} = m!{k - m - 1 \choose n}:\ {\LARGE ?}}$.

\begin{align} &\bbox[10px,#ffd]{\sum_{i = 0}^{n}\pars{-1}^{i}{k \choose n - i} {\pars{m + i}! \over i!}} = \sum_{i = 0}^{\infty}\pars{-1}^{i}\,\,\, \overbrace{\bracks{z^{n - i}}\pars{1 + z}^{k}}^{\ds{k \choose n - i}}\,\,\, \overbrace{m!{m + i \choose i}}^{\ds{\pars{m + i}! \over i!}} \\[5mm] = &\ m!\bracks{z^{n}}\pars{1 + z}^{k}\sum_{i = 0}^{\infty}{m + i \choose i} \pars{-z}^{i} \\[5mm] = &\ m!\bracks{z^{n}}\pars{1 + z}^{k}\sum_{i = 0}^{\infty} \overbrace{{-m - i + i - 1 \choose i}\pars{-1}^{i}}^{\ds{m + i \choose i}} \,\,\,\pars{-z}^{i} \\[5mm] = &\ m!\bracks{z^{n}}\pars{1 + z}^{k}\sum_{i = 0}^{\infty} {-m - 1 \choose i}z^{i} = m!\bracks{z^{n}}\pars{1 + z}^{k}\pars{1 + z}^{-m - 1} \\[5mm] = &\ m!\bracks{z^{n}}\pars{1 + z}^{k - m - 1} = \bbx{m!{k - m - 1 \choose n}} \end{align}