Anonymous

# question on binomial theory..?

hi every1, can any1 prove that (n+1 C r+1) = n C r + (n C r+1)

or explain to me where did this relation come from?

Relevance

First, let's state the meaning of nCr.

Consider n objects. How many ways are there to take r objects from these n objects?

Well, it is called nCr.

Now, with resort to this definition and a little mental idea we can prove the given statement.

It reads that the number of ways to choose (r+1) objects from among (n+1) ones is equal to the number of ways to choose r objects from n objects, plus the number of ways to choose (r+1) objects from among n ones.

Idea: divide the n+1 objects into two groups; one containing one element and the other the rest of the n elements.

Now, the left side (n+1)C(r+1) can be decomposed into the number of ways to choose (r+1) elements from the n elements in the second group above, and the number of ways to choose (r+1) elements from both groups, which means taking the first group unique element and r elements from the second group of n elements. This decomposition translated to mathematical terms reads nC(r+1) + nCr.

(n +1)C (r+1) means the number of combinations of (n +1) things taken (r+1) at a time. Each combination contains (r+1) things.

Let us reserve or remove one thing from the (n +1) things so that we are left with n things.

The number of combinations of (n) things taken (r+1) at a time is nC (r+1).Each combination contains (r+1) things.

The above number combinations are done leaving a particular thing.

If that thing were added we could have more number of combinations.

To find that number of combinations that we have lost, among the n things we take r at a time, so that the number of combinations is nCr. Each combination contains only r things (with out the thing we have reserved).

We add the left thing so that each combination will have (r+1) things.

(n +1)C (r+1) = nC (r+1) +nCr.

(10+1) choose (5+1) = 462

10 choose 5= 252

10 choose 6 = 210

210+252= 462

I am assuming you know how to figure out factorials. I hope this helps.

(n C r) + (n C r+1) = n!/r!(n-r)! + n!/(r+1)!(n-r-1)!

= n!(r+1)/r!(r+1)(n-r)! + n!(n-r)/(r+1)!(n-r)(n-r-1)!

(times (r+1)on the above and below part of 1st term,

times (n-r)on the above and below part of 2nd term)

= n!(r+1)/(r+1)!(n-r)! + n!(n-r)/(r+1)!(n-r)!

= n![(r+1)+(n-r)]/(r+1)!(n-r)!

= n!(n+1)/(r+1)!(n-r)!

= (n+1)!/(r+1)![(n+1)-(r+1))]!

= (n+1 C r+1)