1
$\begingroup$

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ 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. $\endgroup$ – Shalop Sep 14 '17 at 4:56
  • 1
    $\begingroup$ @Beverlie: Do you know $$x_1+x_2+...+x_k=n \\\to\left(\begin{array}{c}n+k-1\\ k-1\end{array}\right)$$ ? $\endgroup$ – Khosrotash Sep 14 '17 at 5:10
  • $\begingroup$ Now I just know due to the help from Khosrotash $\endgroup$ – Beverlie Sep 14 '17 at 5:14
  • $\begingroup$ 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. $\endgroup$ – Martin Sleziak Sep 14 '17 at 5:17
  • $\begingroup$ This does not seem to be a duplicate of the question cited since this question asks for a combinatorial argument. $\endgroup$ – robjohn Sep 15 '17 at 0:55
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ (+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. $\endgroup$ – robjohn Sep 14 '17 at 15:35
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.