# Thread: [SOLVED] Discrete Math Proof: Combinations

1. ## [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.

2. ## nCr Formula

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 for showing us your working. But you have a sign wrong. You should have

$\displaystyle \binom{k}{j}+\binom{k}{j-1}=\frac{k!}{j!(k-j)!} + \frac{k!}{(j-1)!(k-[j-1])!}$

$\displaystyle =\frac{k!}{j!(k-j)!} + \frac{k!}{(j-1)!(k-j\color{red}+\color{black}1)!}$

$\displaystyle =\frac{k!(j-1)!(k-j+1)!+k!j!(k-j)!}{j!(k-j)!(j-1)!(k-j+1)!}$

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

You've obviously got a common factor of $\displaystyle k!$.

What is less obvious is that $\displaystyle j!$ and $\displaystyle (j-1)!$ have a common factor of $\displaystyle (j-1)!$. This is because $\displaystyle j! = (j-1)! \times j$.

And, in the same way, $\displaystyle (k-j+1)! = (k- j)! \times (k-j+1)$.

In all, then, you can take out a common factor $\displaystyle k!(j-1)!(k-j)!$ from the two terms in the numerator to get:

$\displaystyle \frac{k!(j-1)!(k-j+1)!+k!j!(k-j)!}{j!(k-j)!(j-1)!(k-j+1)!}= \frac{ k!(j-1)!(k-j)!([k-j+1] + j)}{ j!(k-j)!(j-1)!(k-j+1)!}$

$\displaystyle =\frac{k!(k+1)}{j!(k+1-j)!}$

$\displaystyle =\frac{(k+1)!}{j!([k+1]-j)!}$

$\displaystyle =\binom{k+1}{j}$