Thread: [SOLVED] Discrete Math Proof: Combinations

Hey, first time poster here, this is the proof:
For positive integers j and k, 1<=j<=k, show that C(k+1,j) = C(k,j) +C(k,j-1)

I am at the point where I have numerator: [ k!(k-j-1)!(j-1)! + k!j!(k-j)! ]
over [ j!(j-1)!(k-j-1)!(k-j)! ]

Which i need to simplify.

Which is supposed to equal (k+1)! / (j!(k+1-j)!) I believe

I'm probably making this more confusing than it needs to be.
Thanks in advance.

Hello jcbeta730

Originally Posted by jcbeta730

Hey, first time poster here, this is the proof:
For positive integers j and k, 1<=j<=k, show that C(k+1,j) = C(k,j) +C(k,j-1)

I am at the point where I have numerator: [ k!(k-j-1)!(j-1)! + k!j!(k-j)! ]
over [ j!(j-1)!(k-j-1)!(k-j)! ]

Which i need to simplify.

Which is supposed to equal (k+1)! / (j!(k+1-j)!) I believe

I'm probably making this more confusing than it needs to be.
Thanks in advance.

Thanks for showing us your working. But you have a sign wrong. You should have







What you need to do now is to factorise the numerator.

You've obviously got a common factor of .

What is less obvious is that and have a common factor of . This is because .

And, in the same way, .

In all, then, you can take out a common factor from the two terms in the numerator to get:









Grandad

Thank you!