Proving a "combinations" formula: [n+1]C[k+1] - nC

lildancergirl22

New member
Joined
Jan 8, 2007
Messages
3
So I have to prove this combinations proof (get the left side to equal the right side) and I have no clue where to even start

. . .\(\displaystyle \L \left(\, \frac{n\, +\, 1}{k\, +\, 1}\, \right)\, -\, \left(\, \frac{n}{k}\, \right)\, =\, \left(\, \frac{n}{k\, +\, 1}\, \right)\)

Where "paren-x-over-y-end-paren" means "x-choose-y".

All I've been told is that nCk can also be:

. . .\(\displaystyle \L \frac{n!}{(n\, -\, k)!\, k!}\)

And the left side can also be:

. . .\(\displaystyle \L \frac{n!}{n\, -\, (k\, +\, 1)!\, (k\, +\, 1)!}\)

Thank you!
_____________________________
Edited by stapel -- Reason for edit: formatting.
 
It is very nearly impossible to read your notation.

If you mean \(\displaystyle {{n+1} \choose {k+1}}{n \choose k} = { n \choose {k+1}}\) then that is not true!

Try to repost your question using C(a,b) to be \(\displaystyle { a \choose b}.\)
 
ok...that didn't work

It's what you have above only on the left side the two sets of brackets are subtracted from each other, not multiplied

thanks
 
\(\displaystyle \L \begin{array}{rcl}
\frac{{\left( {n + 1} \right)!}}{{\left[ {\left( {k + 1} \right)!} \right]\left[ {\left( {n - k} \right)!} \right]}} - \frac{{n!}}{{k!\left( {n - k} \right)!}} & = & \frac{{\left( {n + 1} \right)! - \left( {n!} \right)\left( {k + 1} \right)}}{{\left[ {\left( {k + 1} \right)!} \right]\left[ {\left( {n - k} \right)!} \right]}} \\
& = & \frac{{n!\left[ {\left( {n + 1} \right) - \left( {k + 1} \right)} \right]}}{{\left[ {\left( {k + 1} \right)!} \right]\left[ {\left( {n - k} \right)!} \right]}} \\
& = & \frac{{n!}}{{\left[ {\left( {k + 1} \right)!} \right]\left[ {\left( {n - k - 1} \right)!} \right]}} \\
& = & { n \choose {k+1}} \\
\end{array}\)
 
Top