Simplifying Factorials
Dear LearnMath,
I'm currently working on a proof and ran into a (as far as I can see) simplification problem involving factorials. I'd be very grateful for any help on pointing out if there is a mistake in my reasoning and/or how to solve the simplification. Thanks a lot in advance!
About formatting: since the LaTeX-plug-in does not work for my browser I will be writing the binominal coefficients as (n;k). I hope it is still readable.
The problem:
n is a natural number and k a whole number with 0 < k < n. Prove:
(n+1;k+1) = (n;k+1) + (n;k)
With the help of the formula:
(n;k) = n! / k!(n-k)!
This is my attempt:
Here i just replaced n and k by n+1 and k+1 of the left side of the first equation using the formula above.
(n;k+1) + (n;k) = n! / ((k+1)!(n-k+1)!) + n! / k!(n-k)!
To prove it I have to show that the helping formula (applying to n+1 and k+1 equals to the left side of the first equation:
n+1! / (k+1)!(n-k+2)! = n! / ((k+1)!(n-k+1)!) + n! / k!(n-k)!
Here is where I got stuck, since I'm not used to factorials. I should try to get the denominator to be (k+1)!(n-k+2)!, right? How do I accomplish this? Thanks a lot for your time and for any advice you could offer!
Posted Apr 6, 2012, 5:47 PM UTC
I prefer C(n,k) to (n;k). The defining property of factorials is
a! = a(a-1)! , with 0!=1.
Also,
C(n,k+1) = n!/((k+1)!(n-(k+1)!) = n!/((k+1)!(n-k-1)!)
(You had (n-k+1)! )
So
C(n,k+1) + C(n,k) = n!/((k+1)!(n-k-1)!) + n!/(k!(n-k)!)
Use common denominator
(k+1)!(n-k)!=(k+1)!(n-k)(n-k-1)!=(k+1)k!(n-k)!
Thanks a lot for the correction! I still do not understand your last line.
Those are the denominators of the three different fractions. Where the first denominator slightly differs from mine k+1!((n+1)-(k+1)!). I guess that that's my second mistake, but why is the +1 part not applying for that part of the formula? + I fail to see how they are equal to each other (even taking your values as given). My 'approach' would have been to use a common denominator (which?) for
for it to yield a denominator equal to the first fraction
and hope that the sum equals to
Those ='s are equalities. I used a!=(a-1)! to get them.
Each of the two on the right are one of your original denominators times an extra term, (n-k) for one, (k+1) for the other.
They show you how to multiply the numerators to get the same common denominator, which can be expressed any of the three ways, and also a fourth way
(k+1)!(n-k)!=(k+1)!((n+1)-(k+1))!
Which is the denominator for C(n+1,k+1).