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
It looks simple but I'm baffled and can't reach the correct proof. Thank you.
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
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.
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
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.