0
$\begingroup$

I have proved by induction on k that : $$ \binom{n}{n} + \binom{n+1}{n} + \binom{n+2}{n}+ ... + \binom{n+k}{n} = \binom{n+k+1}{n+1} $$

But now, I need to prove it using a combinatorial argument. Could someone give me a hint ? :/

Thank you !

$\endgroup$

marked as duplicate by Brian M. Scott combinatorics Nov 10 '15 at 22:08

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.

  • 2
    $\begingroup$ Consider choosing $n+1$ numbers from $\{1,2,3\dots n+k+1\}$ by splitting into cases where the largest number chosen is : $n,n+1,n+2 ... n+k$. $\endgroup$ – Nicholas Nov 10 '15 at 18:29
  • $\begingroup$ What is meant by a combinatorical argument? Use the definition of "n choose k" (I don't know what its exact name is in English) $\endgroup$ – Alvin Lepik Nov 10 '15 at 18:29
6
$\begingroup$

We have $n+k+1$ different-flavoured doughnuts. We want to choose $n+1$ of them for a healthy breakfast, saving the remaining $k$ for lunch. The number of ways to do this is clearly $\binom{n+k+1}{n+1}$.

We count the number of choices in another way. Line up the doughnuts in a row.

Suppose that our choice includes the first doughnut on the left. Then there are $\binom{n+k}{n}$ ways to choose the others.

Suppose that our choice does not include the first doughnut on the left, but does include the second one. Then there are $\binom{n+k-1}{n}$ ways to choose the others.

Suppose that our choice does not include either of the first two, but does include the third one. Then there are $\binom{n+k-2}{n}$ ways to choose the others.

And so on. Finally, if the choice does not include any of the first $k$ doughnuts, but includes the $(k+1)$-th ,we must use all the rest, and there are $\binom{n}{n}$ ways to do it.

Add up. We get (backwards) the sum on the left.

$\endgroup$

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