Question

Prove that
C(n+1,r) = C(n,r)+ C(n,r-1)

~~~~~
I know the defintion of a combination is... C= n!/(n-r)!r! but i still cant get left side to equal right side. help.

Answer 1

http://answers.yahoo.com/question/index?qid=20071130201604AAy0UBp

That should guide you. IT is not exactly the same, but you can follow it.

Answer 2

defn.
C(n,r) = n!/((n-r)!r!)

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

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

now recall that something like 5x4! = 5!
then in the same way if I have n! and multiply it by n+1 I would get (n+1)!

so back to
RS = n!/((n-r)!r!) + n!/((r-1)!(n-r-1)!)
I will multiply the top and bottom of the first fraction by
(n-r+1)
and I will multiply the top and bottom of the second fraction by r
simplifying this (without typing that mess) I get
RS = n!(n-r+1)/((n-r=1)!r!) + (n!r/(n-r+1)!r!)
notice we now have a common denominator, so we add up the top.
But I see a common factor of n! in the top , so
RS = n!(n-r+1 - r)/((n-r+1)!r!)
= n!(n+1)/((n-r+1)!r!)
= (n+1)!/((n-r+1)!r!)
= LS