Prove that for m > 0, the following identity holds: $\sum_{k=0}^m (-1)^{m-k}{n+k-1\choose k}{n\choose m-k} = 0$

Question

How shall I tackle this proof? I would brute force it because my knowledge is minimal. Can this one be done combinatorially? How to proceed with the alternating sign has stumped me as well.

Answer 1

Start by manipulating the summand \begin{eqnarray*} \binom{n+k-1}{k} \binom{n}{m-k}= \frac{n}{m} \binom{m}{k} \binom{n-k-1}{m-1}. \end{eqnarray*} Now express the second binomial coefficient as the coefficient of the a function \begin{eqnarray*} \binom{n-k-1}{m-1} = [x^{m-1}]: (1+x)^{n-k-1} \end{eqnarray*} So \begin{eqnarray*} \sum_{k=0}^{m} (-1)^{m-k} \binom{m}{k} \binom{n-k-1}{m-1} &=& \frac{(-1)^{m}n}{m} \sum_{k=0}^{m} (-1)^{k}\binom{m}{k} \binom{n-k-1}{m-1} \\ &=& \frac{(-1)^{m}n}{m} [x^{m-1}]: \sum_{k=0}^{m} (-1)^{k}\binom{m}{k} (1+x)^{n-k-1} \\ &=& \frac{(-1)^{m}n}{m} [x^{m-1}]: (1+x)^{n-1} \left( 1- \frac{1}{1+x} \right)^m \\ &=& \frac{(-1)^{m}n}{m} [x^{m-1}]: (1+x)^{n-m-1} x^m =\color{red}{0}. \\ \end{eqnarray*}

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}$ \begin{align} &\bbox[#ffd,10px]{\ds{% \sum_{k = 0}^{m}\pars{-1}^{m - k}{n + k - 1 \choose k}{n \choose m - k}}} = \sum_{k = 0}^{\infty}\pars{-1}^{m - k}\ \overbrace{\bracks{{-n \choose k}\pars{-1}^{k}}} ^{\begin{array}{l} \mbox{Negating} \\ \mbox{the Binomial} \end{array}}\ {n \choose m - k} \\[5mm] = &\ \pars{-1}^{m}\sum_{k = 0}^{\infty} {-n \choose k}\bracks{z^{m - k}}\pars{1 + z}^{n} = \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{n}\sum_{k = 0}^{\infty} {-n \choose k}z^{k} \\[5mm] = &\ \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{n}\pars{1 + z}^{-n} = \pars{-1}^{m}\bracks{z^{m}}z^{0} = \bbx{\delta_{m0}} \end{align}