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$

I have a dilemma here, how can we show Pascal's Rule :

Show that $$ \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}, 1 \leq r \leq n. $$

I tried solving the right side by substituting everything into the combination's formula but everything gets complicated.. thanks

PS: I tried substituting real valued numbers, and it works, but it should be proof by means of mathematical manipulation.

share|cite|improve this question

marked as duplicate by mixedmath, Srivatsan, pedja, Davide Giraudo, David Mitra Jan 22 '12 at 14:01

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.

tnx. kannapan sampth – IvanMatala Jan 22 '12 at 13:56

1 Answer 1

I'm sure this question has been asked before, but I can't find it.

I think the easiest way to prove this identity is with a combinatorial proof. So we count the same thing in 2 ways. Suppose we have $n$ objects and we are choosing $r$ of them. The left side is that straight out.

Suppose we designate one particular element (it doesn't matter which one, but call it X). Then when choosing $r$ of the $n$ elements, we either have X or we don't. If we do, then we choose $r-1$ of the remaining $n-1$ elements. If we don't, then we choose $r$ of the remaining $n-1$ elements.

Adding these together, we see that the identity follows.

share|cite|improve this answer
Oh - he found the duplicate. Vote to close! (But I keep my answer for posterity) – mixedmath Jan 22 '12 at 13:56

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