Sign up ×
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|cite|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 – repwn Nov 27 '11 at 17:13
A proof using binomial theorem can be found here: – Martin Sleziak Nov 27 '11 at 17:39
Actually, you should tell us the definition of binomial coefficient you want to use. Since, in one interpretation, this is the definition. – GEdgar Nov 27 '11 at 17:56

3 Answers 3

up vote 15 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)^\text{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|cite|improve this answer

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|cite|improve this answer
One man's definition might well be another man's theorem. – ncmathsadist Jan 16 '12 at 15:01

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|cite|improve this answer
Great. Provided this is the definition of binomial coefficient. Until the OP returns, we don't know. – GEdgar Nov 27 '11 at 19:55

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