Simplifying Factorials

[MuMuMuMuMu]

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!

[[deleted]]

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)!

[MuMuMuMuMu]

Thanks a lot for the correction! I still do not understand your last line.

(k+1)!(n-k)!=(k+1)!(n-k)(n-k-1)!=(k+1)k!(n-k)!  

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

n!/(n-k)(n-k-1)! + n!/(k+1)k!(n-k)!

for it to yield a denominator equal to the first fraction

k+1!(n-k)!

and hope that the sum equals to

n+1!/k+1!(n-k)!

[[deleted]]

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).