# Binomial identity?

$${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...)

• Why do you think this is true? Dec 4, 2023 at 20:42
• @ThomasAndrews See edit on how it was derived. Dec 4, 2023 at 21:48
• The standard notation is $\min(k,n)$ Dec 5, 2023 at 0:48
• @jjagmath Fixed it. Thank you Dec 5, 2023 at 1:02

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.

• Thank you. So basically since $n>k-1$ (If it wasn't we would need an exclusion) the equality is the equivalent of the straightforward $\sum_{m=1}^{min(k,n)}{k \choose m}{n \choose m}$ $={n+k \choose n} ={n+k \choose k}$. Dec 5, 2023 at 3:32
• You don't need $n>k-1.$ It is true for all $n,k.$ @OlderAmateur Dec 5, 2023 at 4:56
• And your "straightforward" identity isn't true unless you start with $m=0,$ not $m=1.$ Dec 5, 2023 at 4:57
• $m=1$ is a typo. I copy/pasted from my question and forgot to change it accordingly. Dec 5, 2023 at 5:06

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.

• You might be interested in the following MSE link which awaits a solution using PIE. Dec 17, 2023 at 19:06