# Prove combinatorial Identity using a combinatorial argument. [duplicate]

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 !

## marked as duplicate by Brian M. Scott combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); 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.

• 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$. – Nicholas Nov 10 '15 at 18:29
• 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) – Alvin Lepik Nov 10 '15 at 18:29

## 1 Answer

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.