Binomial identity?

Question

$${n+k-1 \choose k}=\sum_{m=1}^{min(k,n)}{k-1 \choose m-1}{n \choose m} $$

Is there a simple way to demonstrate this equality?

Context

These are two ways of expressing the $x^k$ coefficients in $(1+x+x^2+x^3+\cdots+x^k)^n $. The first term can be obtained using a power series as explained here. The 2nd term is my attempt to obtain the coefficient using the multimonial theorem (still working on a way to show an exclusion with this method).

Edit

How to derive the 2nd term: $$\sum_{m=1}^{min(k,n)}{k-1 \choose m-1}{n \choose m} $$ Given: $$(1+x+x^2+x^3+\cdots+x^{k})^{n}$$ To get the $x^{10}$ coefficient we will attempt to tabulate every permutation that sums to $10$ and calculate its value with the multinomial theroem. How many permutations are there using one term, then how many using two terms... we get this:

\begin{array} {|r|r|}\hline Terms & Permutations & Multinomial Value \\ \hline 1 & 1/1! & n!/(n-1)! \\ \hline 2 & 9/2! & n!/(n-2)! \\ \hline 3 & 36/3! & n!/(n-3)! \\ \hline 4 & 84/4! & n!/(n-4)! \\ \hline 5 & 126/5! & n!/(n-5)! \\ \hline 6 & 126/6! & n!/(n-6)! \\ \hline 7 & 84/7! & n!/(n-7)! \\ \hline 8 & 36/8! & n!/(n-8)! \\ \hline 9 & 9/9! & n!/(n-9)! \\ \hline 10 & 1/10! & n!/(n-10)! \\ \hline \end{array}

Which can be expressed as $$\sum_{m=1}^{k}{{k-1 \choose m-1}\over m!}\cdot{n! \over n-m!}$$ Which simplifies to $$\sum_{m=1}^{k}{k-1 \choose m-1}{n \choose m} $$

(Having read Euler's paper here I thought I might've come up with an improved algorithm, then i discovered power series...)

Answer 1

If we substitute $\binom{n+k-1}{k}=\binom{n+k-1}{n-1}$ and $\binom nm=\binom n{n-m},$ this amounts to counting two ways the number of subsets of size $n-1$ from a set of size $n+k-1.$

Specifically, the right side counts the number of such subsets with $m-1$ elements from the first $k-1$ elements, and $n-m$ elements from the rest.

Answer 2

Here we have a Chu-Vandermonde Identity in disguise.

We obtain for $k>0$ and $n\geq 0$: \begin{align*} \color{blue}{\sum_{m\geq 1}}\color{blue}{\binom{k-1}{m-1}\binom{n}{m}}&=\sum_{m\geq 1}\binom{k-1}{k-m}\binom{n}{m}\tag{1}\\ &=\sum_{m\geq 0}\binom{k-1}{k-m}\binom{n}{m}\tag{2}\\ &\,\,\color{blue}{=\binom{n +k-1}{k}}\tag{3} \end{align*} and the claim follows.

Comment:

• In (1) we write the summation using the index $m\geq 1$ which is admissible, since $\binom{k-1}{m-1}=0$ if $m>k$. We also apply the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (2) we start the summation with $m=0$ noting that $\binom{k-1}{k}=0$.

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