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

Solution 1:

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.

Solution 2:

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.

Solution 3:

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

Solution 4:

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