# Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity

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

Need to give a combinatorial proof

a) in terms of subsets

b) by interpreting the parts in terms of compositions of integers

I should not use induction or any other ways...

-

HINTS:

1. Consider a $k$-element subset of $[n+k]=\{1,\dots,n+k\}$; it has a maximum element, which can be anything from $k$ through $n+k$. How many such subsets are there with maximum element $k+i$ for $i=0,\dots,n$?

2. There are $\binom{k-1+i}{k-1}$ compositions of $k+i$ with $k$ terms. There are $\binom{n+k}k$ compositions of $n+k+1$ with $k+1$ terms.

-
2)Let's split n+k into two parts: 1 and n+k-1. including 1, we have $\binom{n+k-1}{k-1}$, otherwise $\binom{n+k-1}{k}$. Hence $\binom{n+k}{k}$= $\binom{n+k-1}{k-1}$+$\binom{n+k-1}{k}$ Using $\binom{n+k-1}{k}$,repeat the procedure till $\binom{k-1}{k-1}$. 1)I'm still confused here. I understand that the answer to your question should be the identity, however I don't quite understand how this works. – John Lennon Mar 5 '13 at 22:09
(1) Oops: the maximum should have been $k+i$, not $k-1+i$. If $k+i$ is the maximum element of a $k$-element subset of $[n+k]$, the other $k-1$ elements can be any $k-1$ elements of the set $[k-1+i]$, and there are $\binom{k-1+i}{k-1}$ of them. Thus, the summation is just counting the $k$-element subsets of $n+k$ in groups corresponding to their maximum elements. (2) You’re suggesting an informal proof by induction, not a combinatorial argument. You do not want an argument by induction; you want to show that the two sides are counting the same set of compositions in two different ways. – Brian M. Scott Mar 5 '13 at 22:15
"There are $\binom{k-1+i}{k-1}$ compositions of $k+i$ with $k$ terms. There are $\binom{n+k}k$ compositions of $n+k+1$ with $k+1$ terms." Is this already an answer? If so could you explain it to me? – John Lennon Mar 19 '13 at 23:20
@vercammen: Suppose that you have a composition of $n+k+1$ with $k+1$ terms; when you throw away the last term, what’s left is a composition with $k$ terms of some number between $k$ and $k+n$ inclusive. – Brian M. Scott Mar 19 '13 at 23:30
finally clear. thank you! – John Lennon Mar 19 '13 at 23:42

Use $\binom{k}{r} = \binom{k-1}{r} + \binom {k-1}{r-1}$ repeatedly on the expansion of sum.

-


-