# $m!n! < (m+n)!$ Proof?

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.

-

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.

-
Thanks a lot! This was very clear :) – MinaHany Jun 8 '12 at 12:50

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.

-
Theophile's answer and yours completed the picture in my head! Thank you :) – MinaHany Jun 8 '12 at 12:51
+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

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

-

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

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

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

-

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.

-