Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that if $m$ and $n$ are positive integers then $m!n! < (m+n)!$

Given hint:

$m!= 1\times 2\times 3\times\cdots\times m$ and $1<m+1, 2<m+2, \ldots , n<m+n$

It looks simple but I'm baffled and can't reach the correct proof. Thank you.

share|improve this question

6 Answers 6

up vote 54 down vote accepted

Notice that $m!n!$ and $(m+n)!$ both have the same number of terms. Let's compare them: $$m!n! = (1 \times 2 \times \ldots \times m) \times (1 \times 2 \times \ldots \times n)$$ $$(m+n)! = (1 \times 2 \times \ldots \times m) \times ((m+1) \times (m+2) \times \ldots \times (m+n))$$

Both expressions have the same first $m$ terms, but after that each term in the second expression is bigger than the corresponding term in the first: $m+1 > 1$, etc.

share|improve this answer
2  
Thanks a lot! This was very clear :) –  MinaHany Jun 8 '12 at 12:50

One-line proof (some details omitted): ${m+n \choose m} > 1$ if $0 < m < n$.

share|improve this answer

Hint $\ \:\rm f(n) > 1\,$ since it is a product of terms $>1,$ via multiplicative telescopy, viz.

$$\begin{eqnarray}\rm f(n)\, =\ f(0) \prod_{k\:=\:1}^{n}\, \frac{f(k)}{f(k-1)} &=&\rm \, \color{red}{\rlap{--}f(0)}\frac{\color{green}{\rlap{--}f(1)}}{\color{red}{\rlap{--}f(0)}}\frac{\color{royalblue}{\rlap{--}f(2)}}{\color{green}{\rlap{--}f(1)}}\frac{\phantom{\rlap{--}f(3)}}{\color{royalblue}{\rlap{--}f(2)}}\, \cdots\, \frac{\color{brown}{\rlap{--}f(n-1)}}{\phantom{\rlap{--}f(n-2)}}\frac{f(n)}{\color{brown}{\rlap{----}f(n-1)}}\\ &=&\rm\,\ \frac{1+m}1\ \frac{2+m}2\ \frac{3+m}3\,\cdots\, \frac{n+m}n \\ \rm \phantom{\frac{\frac{1}1}{\frac{1}1}}because\ the\ term\ ratio\ is\ \ \displaystyle\rm\ \frac{f(k)}{f(k-1)} &=&\rm\ \frac{(k+m)!}{k!\,m!}\, \frac{(k-1)!\,m!}{(k-1+m)!}\, =\, \frac{k+m}{k} \end{eqnarray} $$

This yields precisely the same proof as the accepted answer. However, by using the general method of telescopy, one is able to derive the proof algorithmically vs. ad-hoc. Such telescopic methods work much more generally. They are essential in more complex problems where ad-hoc methods have no hope due to the innate structure being obfuscated by the complexity. See here for more.

share|improve this answer

Note that $\frac{(m+n)!}{m!}=(m+1)(m+2)\ldots(m+n)$. So you need to prove $n!<(m+1)(m+2)\ldots(m+n)$, and your hint applies.

Alternative proof: if you have $m$ girls and $n$ boys, you can line them up in $m!n!$ ways such that all girls come before all boys, and in $(m+n)!$ ways without that restriction.

share|improve this answer
    
Theophile's answer and yours completed the picture in my head! Thank you :) –  MinaHany Jun 8 '12 at 12:51
1  
+1 Your observation about boys and girls is just what I would have said if you hadn't said it first. –  Michael Hardy Jun 8 '12 at 12:56
    
I think you mean $(m+n)!/m!$ and $n! < ...$ on the second line? –  UncleZeiv Jun 8 '12 at 13:30
    
@UncleZeiv: Yep, and the final $n$'s in the products needed to be $m+n$ as well. Now corrected. Thanks. –  Marc van Leeuwen Jun 8 '12 at 13:34
    
Or said differently: $\frac{(m+n)!}{m! n!} = \binom{m+n}{m} >1$ because there is more than $1$ way to choose $m$ objects from $m+n$ when $m,n$ are positive. –  Mike F Jun 9 '12 at 0:19

Some quite complicated answers here for showing that there is more than one string we can form with letters $A$ and $B$ of length $m+n$, with $m$ repetitions of $A$ and $n$ repetitions of $B.$

share|improve this answer

If you would like, here is an other proof:

I assume that $n,m\in\mathbb{N}_0$. From the hint that $$ 1<m+1, 2<m+2, \ldots, n<m+n $$ you can see that $n!<(m+n)!$.

Now we proof by induction that $m!n!<(m+n)!$. Take $m=1$, then we have $1!n!<(1+n)!$. Now assume that $m!n!<(m+n)!$ is correct, this is the induction hypothesis. We calculate \begin{align*} (m+1)!n!&=(m+1)m!n!\\&<(m+1)(m+n)!\\&<(m+n+1)(m+n)!\\&=(m+n+1)!. \end{align*} The first inequality is because of the induction hypothesis. The second because $n\geq1$.

share|improve this answer
    
Thanks! It is helpful to see the same proof in induction as well. –  MinaHany Jun 8 '12 at 12:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.