Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

Please help.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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  
(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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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