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.

Possible Duplicate:
Proving ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

can someone explain to me the proof of $${n+1\choose k} = {n\choose k} + {n\choose k-1}$$ Thanks in advance!

share|improve this question

marked as duplicate by Zhen Lin, Jack Schmidt, robjohn, Mike Spivey, Jonas Meyer Nov 27 '11 at 22:44

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.

"Actually I don't really need the explanation of the proof, I just need the proof itself", I don't think we need this sort of questions on the site. Voting to close. –  Asaf Karagila Nov 27 '11 at 17:21
-1: We have nothing against homework questions per se, but explicitly declaring that you have no interest in understanding the problem and just want a proof you can copy, that crosses the line. –  Henning Makholm Nov 27 '11 at 17:22
@Asaf I can think of many cases where one might want a proof without - at the moment - needing a detailed explanation, e.g. if the result was some minor step in another result. Moreover, the OP has explicitly said that it is not homework. As such I think it was wrong to close this question. –  Bill Dubuque Nov 27 '11 at 17:57
@Asaf I think the site would work much more smoothly if everyone strives to avoid extramathematical matters. Straying into matters close to censorship based upon extramathematical subjective criteria can only lead to problems. Imo, an on-topic question should always be welcome, no matter its source, motivation, grammar, etc. –  Bill Dubuque Nov 27 '11 at 18:18
I've voted to re-open. In the notice explaining that it was closed, it says "This question is unlikely to ever help any future visitors". That doesn't make any sense at all. It seems as if closure resulted from people misunderstanding the poster's comments as meaning he doesn't want to understand the proof but just wants to copy it so he can turn it in. –  Michael Hardy Nov 27 '11 at 19:01
show 16 more comments

3 Answers

up vote 14 down vote accepted

One proof goes like this: Suppose you have a list of all $\dbinom {n}{k-1}$ ways to choose $k-1$ objects out of $n$. Then we add an $(n+1)$th object to those from which we can choose. How do we make a list of all $\dbinom{n+1}{k}$ ways to choose $k$ out of these $n+1$? Here's how: first make a list of all ways to choose $k$ out of the original $n$ objects. That's a partial list. All of its items exclude the "new" object. It has $\dbinom nk$ items. Then take the list you already had, of all ways to pick $k-1$ out of those $n$. To each item on the list, giving $k-1$ objects, you add the "new" object, getting a set of $k$ of the $n+1$. That's another partial list. All of its items include the "new" object. It has $\dbinom{n}{k-1}$ items.

Now just add the two partial lists together: the list of those that exclude the "new" object----there are $\dbinom nk$ of those----and the list of those that include the "new" object---there are $\dbinom{n}{k-1}$ of those.

share|improve this answer
add comment

The identity is true by vacuity, because that's how my teacher defines a binomial coefficient. [Actually, one needs to append the base conditions to that for a complete definition.]

On a serious note, please define the notation that you use. As I demonstrated just now, an otherwise interesting question could become trivial for such mundane reasons as differing definitions or conventions.

share|improve this answer
One man's definition might well be another man's theorem. –  ncmathsadist Jan 16 '12 at 15:01
add comment

I'll just be completely unimaginative here:

$$\eqalign{{n\choose k}+{n\choose k-1}&= {n!\over (n-k)!k!}+ {n!\over (n-(k-1))! (k-1)!}\cr &={n!\over (n-k)!k!}+ {n!\over (n-k+1)! (k-1)!}\cr &={(n-k+1)n!\over(n-k+1) (n-k)!k!}+ {n!k\over (n-k+1)! (k-1)! k}\cr &={(n-k+1)n! + n!k\over (n-k+1)! k!}\cr &={n\cdot n !-kn!+n!+n!k\over (n-k+1)! k!}\cr &={n\cdot n ! +n! \over (n-k+1)! k!}\cr &={n!(n+1) \over (n-k+1)! k!}\cr &={(n+1)! \over( (n+1)-k)! k!}\cr &={n+1\choose k}. }$$

share|improve this answer
+1 for the initial comment. –  Michael Hardy Nov 27 '11 at 18:06
Great. Provided this is the definition of binomial coefficient. Until the OP returns, we don't know. –  GEdgar Nov 27 '11 at 19:55
add comment

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