1
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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}$. $\endgroup$ Dec 5, 2023 at 3:32
  • $\begingroup$ You don't need $n>k-1.$ It is true for all $n,k.$ @OlderAmateur $\endgroup$ Dec 5, 2023 at 4:56
  • 1
    $\begingroup$ And your "straightforward" identity isn't true unless you start with $m=0,$ not $m=1.$ $\endgroup$ Dec 5, 2023 at 4:57
  • $\begingroup$ $m=1$ is a typo. I copy/pasted from my question and forgot to change it accordingly. $\endgroup$ Dec 5, 2023 at 5:06
2
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .