# Proving combinatorial identity involving counting multisets

$\textbf{Question}:$ Let $n$ and $k$ be nonnegative integers such that $n \ge 1,$ then $$\displaystyle \binom{n - 1}{0} + \binom{n}{1} + \binom{n + 1}{2} + \dots + \binom{n + k - 1}{k} = \binom{n + k}{k} \; \; \; \; \; \; \; (\ast)$$

I ran into this problem while trying to prove the formula involving counting multisets. In general, the number of ways to form $k$-elements multisets from an $n$-elements set, denoted by $M(n, k)$ where $n \ge 1,$ is $\displaystyle \binom{n + k - 1}{k}.$ I am attempting to prove this fact using proof by strong induction on $n,$ which eventually leads to proving that $(\ast)$ is true, but I currently stuck on proving $(\ast).$ Can someone provide me some hints to tackle $(\ast)?$

Also, $(\ast)$ implies that $\displaystyle M(n + 1, k) = \sum_{i = 0}^{k} \; M(n, i).$

• This is the hockey stick identity. – Lee David Chung Lin Sep 9 '16 at 3:35
• @LeeDavidChungLin How so? I found the identity you mention here (artofproblemsolving.com/wiki/index.php/Combinatorial_identity) but it doesn't seem to match the formula in $(\ast)$ – user298251 Sep 9 '16 at 5:37
• $\text{Your expression} = {n-1 \choose n-1} + {n \choose n-1} + {n+1 \choose n-1} + \ldots + {n+k-1 \choose n-1}$ so your $n-1$ is that page's $r$ and their $n$ is your $n+k-1$. – Lee David Chung Lin Sep 9 '16 at 5:51
• Oh yes thank you for pointing that out! I actually used that identity you mentioned earlier in my induction proof to arrive at $(\ast),$ but this time I didn't recognize that identity. – user298251 Sep 9 '16 at 6:09
• yeah, you had your last line of the post right there since the beginning, which of course is another equivalent form. – Lee David Chung Lin Sep 9 '16 at 6:39

The left hand side is the coefficient of $x^k$ in \begin{align*} x^k(1+x)^{n-1}+x^{k-1}(1+x)^n &+ \cdots + (1+x)^{n+k-1} = x^k(1+x)^{n-1}\frac{\left(1-\left(\frac{1+x}{x}\right)^{k+1}\right)}{1-\frac{1+x}{x}}\\ &=x^k(1+x)^{n-1}\frac{(1+x)^{k+1}-x^{k+1}}{x^{k}}\\ &= (1+x)^{n+k} - x^{k+1}(1+x)^{n-1} \end{align*} and hence equals $\binom{n+k}{k}$.
So $$\binom{n+k}{k}=\binom{n+(k+1)-1}{(k+1)-1}$$ which is the number of ways to create $n$ with $k+1$ summands(allowing $0$ as a summand).
So, lets denote $A_{n,k+1}$ the sets of those tuples(each elements in the tuple is like a summand).
So, you have to prove that $A_{n,k+1}=\phi(\bigcup _{i=0}^k A_{n-1,i+1})$ where $\phi$ is defined as $\phi ((x_1,x_2,\ldots ,x_r))=(x_1,x_2,\ldots ,x_r+1,\underbrace {0,\ldots ,0}_{\text{$k+1-r$times}})$. By adding principle, you will get your resut.
HINT: $\binom{n-1+i}i=\binom{n-1+i}{n-1}$ is the number of $n$-element subsets of $\{1,2,\ldots,n+k\}$ whose largest element is $n+i$. What is $\binom{n+k}n$?