Proving Combinations Formula | Step-by-Step Guide and Examples

[Government$]

Homework Statement

Prove the following:

\frac{n!}{m!(n-m)!} = \frac{n!}{(m-2)!(n-m + 2)!} + 2* \frac{(n-1)!}{(m-1)!(n-m)!} + \frac{(n-2)!}{(m-2)!(n-m)!}

The Attempt at a Solution

I tried writing following

\frac{n!}{m!(n-m)!} = \frac{n!}{m!(n-m)!}(\frac{m(m-1)}{(n-m + 2)(n-m + 1)} + \frac{2m}{n} + \frac{m(m-1)}{n(n-1)})

Now i should get \frac{m(m-1)}{(n-m + 2)(n-m + 1)} + \frac{2m}{n} + \frac{m(m-1)}{n(n-1)} = 1
but i don't get 1. Any other ideas?

 

[SteamKing]

Hint: m! = m * (m-1) * (m-2)!

 

[Government$]

I know that, but where to use it?

 

[tiny-tim]

your m(m-1)/n(n-1) is wrong

 

[Government$]

I rechecked it two or three time i really don't see how it is wrong.

 

[SammyS]

Homework Statement

Prove the following:

\frac{n!}{m!(n-m)!} = \frac{n!}{(m-2)!(n-m + 2)!} + 2* \frac{(n-1)!}{(m-1)!(n-m)!} + \frac{(n-2)!}{(m-2)!(n-m)!}

What is the lowest common denominator for the right-hand side ?

The Attempt at a Solution

I tried writing following

\frac{n!}{m!(n-m)!} = \frac{n!}{m!(n-m)!}(\frac{m(m-1)}{(n-m + 2)(n-m + 1)} + \frac{2m}{n} + \frac{m(m-1)}{n(n-1)})

Now i should get \frac{m(m-1)}{(n-m + 2)(n-m + 1)} + \frac{2m}{n} + \frac{m(m-1)}{n(n-1)} = 1
but i don't get 1. Any other ideas?

 

[Government$]

(m-1)!(n-m+2)!

 

[Government$]

I don't understad why, since (m-2)! doesn't contain (m-1) nor (n-m)! contains (n-m+2)! or (n-m+1)!

 

[Government$]

If i want get whole expression under one fraction i should multply first fraction with (m-1)/(m-1) to get n!(m-1)/(m-1)!(n-m+2)! , second fraction with (n-m+2)(n-m+1)/(n-m+2)(n-m+1) to get
(n-1)!(n-m+2)(n-m+1)/(m-1)!(n-m+2)! , and third with (m-1)(n-m+2)(n-m+1)/(m-1)(n-m+2)(n-m+1)
to get (n-2)!(m-1)(n-m+2)(n-m+1)/(m-1)!(n-m+2)!

 

[SammyS]

I don't understad why, since (m-2)! doesn't contain (m-1) nor (n-m)! contains (n-m+2)! or (n-m+1)!

You were correct. I deleted my post, but you must have seen it before I deleted it.

 

[SammyS]

If i want get whole expression under one fraction i should multply first fraction with (m-1)/(m-1) to get n!(m-1)/(m-1)!(n-m+2)! , second fraction with (n-m+2)(n-m+1)/(n-m+2)(n-m+1) to get
(n-1)!(n-m+2)(n-m+1)/(m-1)!(n-m+2)! , and third with (m-1)(n-m+2)(n-m+1)/(m-1)(n-m+2)(n-m+1)
to get (n-2)!(m-1)(n-m+2)(n-m+1)/(m-1)!(n-m+2)!

That's virtually unreadable as it is written. Break it up into separate lines & give it some space...

As follows:

If i want get whole expression under one fraction i should multiply:

first fraction with (m-1)/(m-1) to get

n!(m-1)/(m-1)!(n-m+2)! ,​

second fraction with (n-m+2)(n-m+1)/(n-m+2)(n-m+1) to get

(n-1)!(n-m+2)(n-m+1)/(m-1)!(n-m+2)! ,​

and third with (m-1)(n-m+2)(n-m+1)/(m-1)(n-m+2)(n-m+1)
to get

(n-2)!(m-1)(n-m+2)(n-m+1)/(m-1)!(n-m+2)!​

So the numerator is (m-1)n! + 2(n-m+2)(n-m+1)(n-1)! + (m-1)(n-m+2)(n-m+1)(n-2)! .

There's a common factor of (n-2)! , right?

 

[Government$]

After that i get (n-2)!*(n(n-1)(m-1) + 2(n-m+2)(n-m+1)(n-1) + (m-1)(n-m+2)(n-m+1))/(m-1)!(n-m+2)!

i tried and i can't find any other common factor in numerator and i have common factors between two products such as (n-1) , (m-1), (n-m+2)(n-m+1). Only other way is to multiply everything and then try to factor out something that will cancel m-1 and (n-m+2)(n-m+1) in denominator.

 

[haruspex]

\frac{n!}{m!(n-m)!} = \frac{n!}{(m-2)!(n-m + 2)!} + 2* \frac{(n-1)!}{(m-1)!(n-m)!} + \frac{(n-2)!}{(m-2)!(n-m)!}

Have you checked whether it even seems to be true? Try n=m=2.

 

[SammyS]

Have you checked whether it even seems to be true? Try n=m=2.

I was about to ask a similar question.

This may also be what tiny-tim was suggesting.Is there a typo in your expression?

In terms of binomial coefficients, what the OP states is that you are trying to prove that

\displaystyle \ \binom{n}{m}=\binom {n} {m-2}+2\binom {n-1} {m-1}+\binom {n-2} {m-2}\ .

 

[Government$]

I was about to ask a similar question.

This may also be what tiny-tim was suggesting.


Is there a typo in your expression?

In terms of binomial coefficients, what the OP states is that you are trying to prove that

\displaystyle \ \binom{n}{m}=\binom {n} {m-2}+2\binom {n-1} {m-1}+\binom {n-2} {m-2}\ .

That is exactly what i need to prove, i just didn't know how to write it like that using Latex. Here is full text of problem:

Prove that \displaystyle \ \binom{n}{m}=\binom {n} {m-2}+2\binom {n-1} {m-1}+\binom {n-2} {m-2}\ n\geq2, m \geq2

When i plug in n=m=2 i get \frac{0}{0} = \frac{2}{0} + \frac{2}{0} + \frac{0}{0}

 

[haruspex]

Prove that \displaystyle \ \binom{n}{m}=\binom {n} {m-2}+2\binom {n-1} {m-1}+\binom {n-2} {m-2}\ n\geq2, m \geq2

When i plug in n=m=2 i get \frac{0}{0} = \frac{2}{0} + \frac{2}{0} + \frac{0}{0}

No, 0! = 1. \binom{0}{0} = \binom{2}{0} = 1

 

[Government$]

Yea, i overlooked that. With that in mind.

Let n=m=2

\frac{2!}{2!(2-2)!} = \frac{2!}{(2-2)!(2-2 + 2)!} + 2* \frac{(2-1)!}{(2-1)!(2-2)!} + \frac{(2-2)!}{(2-2)!(2-2)!}

\frac{1}{1(0)!} = \frac{1}{(0)!1} + 2* \frac{1}{1(0)!} + \frac{(0)!}{(0)!(0)!}

1 = 1 + 2 + 1

1 = 4

 

[SammyS]

That is exactly what i need to prove, i just didn't know how to write it like that using Latex. Here is full text of problem:

Prove that \displaystyle \ \binom{n}{m}=\binom {n} {m-2}+2\binom {n-1} {m-1}+\binom {n-2} {m-2}\ n\geq2, m \geq2

When i plug in n=m=2 i get \frac{0}{0} = \frac{2}{0} + \frac{2}{0} + \frac{0}{0}

Do you suppose the problem should have been to prove

\displaystyle \ \binom{n}{m}=\binom {n-2} {m-2}+2\binom {n-2} {m-1}+\binom {n-2} {m}\,,\ n\geq2, m \geq2 \ ?

 

[Government$]

Maybe i will try to slove it,

This problem should be difficult according to my textbook, here is a pic from my textbook:

http://img444.imageshack.us/img444/8316/img00121201304241927.jpg

 

[Government$]

Do you suppose the problem should have been to prove

\displaystyle \ \binom{n}{m}=\binom {n-2} {m-2}+2\binom {n-2} {m-1}+\binom {n-2} {m}\,,\ n\geq2, m \geq2 \ ?

I managed to prove this without much problem.
Probably it is a typo in my textbook.