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