Proof of combinations

1. Apr 23, 2013

Government$1. The problem statement, all variables and given/known data 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)!}$ 3. 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 dont get 1. Any other ideas? 2. Apr 23, 2013 SteamKing Staff Emeritus Hint: m! = m * (m-1) * (m-2)! 3. Apr 23, 2013 Government$

I know that, but where to use it?

4. Apr 23, 2013

tiny-tim

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

5. Apr 23, 2013

Government$I rechecked it two or three time i really don't see how it is wrong. 6. Apr 23, 2013 SammyS Staff Emeritus What is the lowest common denominator for the right-hand side ? 7. Apr 23, 2013 Government$

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

8. Apr 23, 2013

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)! 9. Apr 23, 2013 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)!

10. Apr 23, 2013

SammyS

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

11. Apr 23, 2013

SammyS

Staff Emeritus
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?

12. Apr 23, 2013

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. 13. Apr 23, 2013 haruspex Have you checked whether it even seems to be true? Try n=m=2. 14. Apr 23, 2013 SammyS Staff Emeritus 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}\ .$ 15. Apr 23, 2013 Government$

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}$

16. Apr 23, 2013

haruspex

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

17. Apr 23, 2013

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$ 18. Apr 24, 2013 SammyS Staff Emeritus 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 \ ?$ 19. Apr 24, 2013 Government$

Maybe i will try to slove it,

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

http://img444.imageshack.us/img444/8316/img00121201304241927.jpg [Broken]

Last edited by a moderator: May 6, 2017
20. Apr 24, 2013

Government\$

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