Intereting Posts

Symmetric Matrices with trace zero
A unsolved puzzle from Number Theory/ Functional inequalities
Why do we need Hausdorff-ness in definition of topological manifold?
Show finite complement topology is, in fact, a topology
On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in $, with diagonal moves allowed
Alternating series test for complex series
When is the canonical extension of scalars map $M\to S\otimes_RM$ injective?
Example of two convergent series whose product is not convergent.
Topology needed for differential geometry
Reference Request: Finding an Op-Ed by J. Hammersley
Equivalence of Definitions of Principal $G$-bundle
Local vs. global in the definition of a sheaf
Integral $\int_0^1\frac{\arctan^2x}{\sqrt{1-x^2}}\mathrm dx$
How do I prove that $f(x)f(y)=f(x+y)$ implies that $f(x)=e^{cx}$, assuming f is continuous and not zero?
Should a Cantor diagonal argument on a list of all rationals always produce an irrational number?

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$

- $n$ choose $k$ where $n$ is less than $k$
- Proof of Stirling's Formula using Trapezoid rule and Wallis Product
- Factorial sum estimate $\sum_{n=m+1}^\infty \frac{1}{n!} \le \frac{1}{m\cdot m!}$
- Closed form for $(p-n)!\pmod{p}$ where $p$ is prime
- Why does the sum of the reciprocals of factorials converge to $e$?
- How many digits are there in 100!?

It looks simple but I’m baffled and can’t reach the correct proof.

Thank you.

- A conjecture concerning primes and algebra
- Find minimum of $P=\frac{\sqrt{3(2x^2+2x+1)}}{3}+\frac{1}{\sqrt{2x^2+(3-\sqrt{3})x +3}}+\frac{1}{\sqrt{2x^2+(3+\sqrt{3})x +3}}$
- Proving that $\phi_a(z) = (z-a)/(1-\overline{a}z)$ maps $B(0,1)$ onto itself.
- Trouble with an Inequality
- An application of Jensen's Inequality
- How prove that $10(a^3+b^3+c^3)-9(a^5+b^5+c^5)\le\dfrac{9}{4}$
- Induction proof of $n^{(n+1) }> n(n+1)^{(n-1)}$
- Proving Holder's inequality using Jensen's inequality
- Given $abc(a+b+c)=3$ prove $(a+b)(b+c)(c+a)>8$
- Is $|f(a) - f(b)| \leqslant |g(a) - g(b)| + |h(a) - h(b)|$? when $f = \max\{{g, h}\}$

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.

- Prove $\forall a,b,c \in \mathbb Z$, if $ab+ac\equiv 3\pmod 6$ then $b \not\equiv c \pmod 6$ by contraposition
- Why is $A^TA$ invertible if $A$ has independent columns?
- What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof?
- Product of two complementary error functions (erfc)
- Prove that $A^TD-C^TB=I$
- Compatibility of topologies and metrics on the Hilbert cube
- Proving $\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$ with induction
- Four complex numbers $z_1,z_2,z_3,z_4$ lie on a generalized circle if and only if they have a real cross ratio $\in\mathbb{R}$
- $\Bbb RP^2$ as the union of a Möbius band and a disc
- Why weak law of large number still alive?
- How do I simplify $\sqrt{3}(\cot 70^\circ + 4 \cos 70^\circ )$?
- Good Textbooks for Real Analysis and Topology.
- What does an outer automorphism look like?
- Why is it useful to show the existence and uniqueness of solution for a PDE?
- Irreducible but not prime in $K/(X^2-Y^3)$