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.
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
http://answers.yahoo.com/question/index?qid=20071130201604AAy0UBp
That should guide you. IT is not exactly the same, but you can follow it.
To prove that C(n+1,r) = C(n,r) + C(n,r-1), let's first expand both sides of the equation using the definition of combination.
Left side: C(n+1,r) = (n+1)! / [(n+1-r)! * r!]
Right side: C(n,r) + C(n,r-1) = n! / [(n-r)! * r!] + n! / [(n-r+1)! * (r-1)!]
Let's simplify the right side to see if it matches the left side:
Right side: [n! * (n-r+1)] / [(n-r)! * r!] + [n! * r] / [(n-r+1)! * (r-1)!]
Now, let's find the common denominator of the two fractions on the right side:
Right side: [n! * (n-r+1) * (n-r)] / [(n-r)! * r! * (n-r+1)] + [n! * r * r] / [(n-r+1)! * (r-1)! * r]
Now, we can combine the two fractions:
Right side: [n! * (n-r+1) * (n-r) + n! * r * r] / [(n-r)! * r! * (n-r+1)]
Next, let's simplify the numerator:
Right side: [n! * (n-r+1) * (n-r) + n! * r * r] / [(n-r)! * r! * (n-r+1)]
= [n! * (n-r+1) * (n-r) + n! * r * r] / [n! * (n-r)! * r! * (n-r+1)]
Now, we can cancel out the common factors:
Right side: [(n-r+1) * (n-r) + r * r] / [(n-r+1)! * r!]
= [(n² - 2nr + r²) + r²] / [(n-r+1)! * r!]
Simplifying further:
Right side: [n² - 2nr + 2r²] / [(n-r+1)! * r!]
Now, let's compare this with the left side:
Left side: (n+1)! / [(n+1-r)! * r!]
We can rewrite (n+1)! as (n+1) * n!
Left side: [(n+1) * n!] / [(n+1-r)! * r!]
Now, notice that (n+1-r)! can be written as (n+1-r) * (n-r)!
Left side: [(n+1) * n!] / [(n+1-r) * (n-r)! * r!]
Now, observe that the numerator of the right side matches the numerator of the left side:
Right side numerator: n² - 2nr + 2r²
Left side numerator: (n+1) * n!
Therefore, we can conclude that:
C(n+1,r) = C(n,r) + C(n,r-1)