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

$\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?

## marked as duplicate by Markus Scheuer, N. F. Taussig, user296602, Jack, Especially LimeSep 14 '17 at 15:46

• Take a look at this question, and generalize the answer given there, i.e., consider $k$-element subsets of $\{1,...,n+k\}$, and partition the collection of all such subsets according to their largest element. – Shalop Sep 14 '17 at 4:56
• @Beverlie: Do you know $$x_1+x_2+...+x_k=n \\\to\left(\begin{array}{c}n+k-1\\ k-1\end{array}\right)$$ ? – Khosrotash Sep 14 '17 at 5:10
• Now I just know due to the help from Khosrotash – Beverlie Sep 14 '17 at 5:14
• Isn't this, after some small transformations, the same sum as this: Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$? You might find something useful also in other posts linked there. – Martin Sleziak Sep 14 '17 at 5:17
• This does not seem to be a duplicate of the question cited since this question asks for a combinatorial argument. – robjohn Sep 15 '17 at 0:55

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}$$

• (+1) Now that I've posted my answer, I see that it is essentially the same as yours, except with stars and bars rather than variables and values. If this is too close for your comfort, I will delete my answer. – robjohn Sep 14 '17 at 15:35

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}$