Combinatoric Proof of $\sum_0^n\binom{k-1+i}{k-1} = \binom{n+k}{k}$

Question

$\sum_0^n\binom{k-1+i}{k-1} = \binom{n+k}{k}$

I think there are two different ways to prove the above identity: one is algebraic and the other one is combinatoric.

I have seen there's some ways to handle this problem with some sort of lattice like structure.

Any advice for approaching this problem in "combinatoric" way?

Answer 1

Suppose $x_1,x_2,...\in \mathbb{N}\cup \{0\}$ and we need to answer numbers of solution of this nequality $$x_1+x_2+x_3+...+x_k\leq n$$ one method is partitioning ,so we have $$x_1+x_2+x_3+...+x_k\leq n (\equiv) \\\to\begin{cases}x_1+x_2+x_3+...+x_k = 0 & \left(\begin{array}{c}0+k-1\\ k-1\end{array}\right)\\x_1+x_2+x_3+...+x_k = 1 & \left(\begin{array}{c}1+k-1\\ k-1\end{array}\right)\\x_1+x_2+x_3+...+x_k =2&\left(\begin{array}{c}2+k-1\\ k-1\end{array}\right)\\\vdots\\x_1+x_2+x_3+...+x_k = n& \left(\begin{array}{c}n+k-1\\ k-1\end{array}\right)\end{cases} $$sum of the is $$\sum_0^n\binom{k-1+i}{k-1} $$ second method to find the number of solution is to add $\bf{x_{k+1}}$ as new variable ,and convert inequality to equation . so $$x_1+x_2+x_3+...+x_k \leq n \space (\equiv)\\ x_1+x_2+x_3+...+x_k +\color{red} {\bf{x_{k+1}}}=n \to \binom{n+(k+1-1}{(k+1)-1}$$ hence $$\sum_0^n\binom{k-1+i}{k-1} =\binom{n+(k+1)-1}{(k+1)-1}=\binom{n+k}{k}$$

Answer 2

Combinatorial Approach

The Stars and Bars Formula says that there are $\binom{k-1+i}{k-1}$ ways to put $i$ stars into $k$ bins. Thus, there are $$ \sum_{i=0}^n\binom{k-1+i}{k-1} $$ $$ \underbrace{\star\star\star\,\mid\,\star\,\mid\,\star\star}_\text{$i$ stars and $k-1$ bars}\qquad\underbrace{\star\star\star\star\star}_\text{$n-i$ stars} $$ ways to put up to $n$ stars into $k$ bins. We can also count this same number by adding a bin to hold the excess $n-i$ stars and get that the number of ways to put the $n$ stars into the $k+1$ bins to be $$ \binom{n+k}{k} $$ $$ \underbrace{\star\star\star\,\mid\,\star\,\mid\,\star\star\,\mid\,\star\star\star\star\star}_\text{$n$ stars and $k$ bars} $$

---

Algebraic Approach $$ \begin{align} \sum_{i=0}^n\binom{k-1+i}{k-1} &=\sum_{i=0}^n\binom{k-1+i}{i}\binom{n-i}{n-i}\tag{1}\\ &=(-1)^n\sum_{i=0}^n\binom{-k}{i}\binom{-1}{n-i}\tag{2}\\ &=(-1)^n\binom{-k-1}{n}\tag{3}\\ &=\binom{k+n}{n}\tag{4}\\ &=\binom{k+n}{k}\tag{5} \end{align} $$ Explanation:
$(1)$: $\binom{n}{k}=\binom{n}{n-k}$ and $\binom{k}{k}=[k\ge0]$
$(2)$: convert to negative binomial coefficients
$(3)$: Vandermonde's Identity
$(4)$: convert from negative binomial coefficients
$(5)$: $\binom{n}{k}=\binom{n}{n-k}$