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

#### Solutions Collecting From Web of "$m!n! < (m+n)!$ Proof?"

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.

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.

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

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.