Putnam 2004, Problem B-2

Let $m$ and $n$ be positive integers. Show that
\[
\frac{(m+n)!}{(m+n)^{m+n}} < \frac{m! \, n!}{m^m \, n^n}.
\]

Solution:
**First solution:** We have
$$(m+n)^{m+n} > \binom{m+n}{m} m^m n^n$$
because the binomial expansion of $(m+n)^{m+n}$ includes the term on the right as well as some others. Rearranging this inequality yields the claim.

**Remark:** One can also interpret this argument combinatorially. Suppose that we choose $m+n$ times (with replacement) uniformly randomly from a set of $m+n$ balls, of which $m$ are red and $n$ are blue. Then the probability of picking each ball exactly once is $(m+n)!/(m+n)^{m+n}$. On the other hand, if $p$ is the probability of picking exactly $m$ red balls, then $p < 1$ and the probability of picking each ball exactly once is $p(m^m/m!)(n^n/n!)$.

**Second solution:** (by David Savitt) Define
$$S_k = \{i/k : i = 1, \ldots, k\}$$
and rewrite the desired inequality as
$$\prod_{x \in S_m} x \prod_{y \in S_n} y > \prod_{z \in S_{m+n}} z.$$

To prove this, it suffices to check that if we sort the multiplicands on both sides into increasing order, the $i$-th term on the left side is greater than or equal to the $i$-th term on the right side. (The equality is strict already for $i = 1$, so you do get a strict inequality above.)

Another way to say this is that for any $i$, the number of factors on the left side which are less than $i/(m+n)$ is less than $i$. But since $j/m < i/(m+n)$ is equivalent to $j < im/(m+n)$, that number is
$$\left\lceil \frac{im}{m+n} \right\rceil - 1 + \left\lceil \frac{in}{m+n} \right\rceil - 1$$
$$\leq \frac{im}{m+n} + \frac{in}{m+n} - 1 = i-1.$$

**Third solution:** Put $f(x) = x(\log(x+1) - \log x)$; then for $x > 0$,
$$f'(x) = \log(1 + 1/x) - \frac{1}{x+1}$$
$$f''(x) = -\frac{1}{x(x+1)^2}.$$

Hence $f''(x) < 0$ for all $x$; since $f'(x) \to 0$ as $x \to \infty$, we have $f'(x) > 0$ for $x > 0$, so $f$ is strictly increasing. Put $g(m) = m\log m - \log(m!)$; then $g(m+1) - g(m) = f(m)$, so $g(m+1) - g(m)$ increases with $m$. By induction, $g(m+n) - g(m)$ increases with $n$ for any positive integer $n$, so in particular
$$g(m+n) - g(m) > g(n) - g(1) + f(m)$$
$$\geq g(n)$$
since $g(1) = 0$. Exponentiating yields the desired inequality.

**Fourth solution:** (by W.G. Boskoff and Bogdan Suceavă) We prove the claim by induction on $m+n$. The base case is $m = n = 1$, in which case the desired inequality is obviously true: $2!/2^2 = 1/2 < 1 = (1!/1^1)(1!/1^1)$. To prove the induction step, suppose $m+n > 2$; we must then have $m > 1$ or $n > 1$ or both. Because the desired result is symmetric in $m$ and $n$, we may as well assume $n > 1$. By the induction hypothesis, we have
$$\frac{(m+n-1)!}{(m+n-1)^{m+n-1}} < \frac{m!}{m^m} \frac{(n-1)!}{(n-1)^{n-1}}.$$

To obtain the desired inequality, it will suffice to check that
$$\frac{(m+n-1)^{m+n-1}}{(m+n-1)!} \frac{(m+n)!}{(m+n)^{m+n}} < \frac{(n-1)^{n-1}}{(n-1)!} \frac{n!}{n^n}$$
or in other words
$$\left(1 - \frac{1}{m+n}\right)^{m+n-1} < \left(1 - \frac{1}{n}\right)^{n-1}.$$

To show this, we check that the function $f(x) = (1 - 1/x)^{x-1}$ is strictly decreasing for $x > 1$; while this can be achieved using the weighted arithmetic-geometric mean inequality, we give a simple calculus proof instead. The derivative of $\log f(x)$ is $\log(1 - 1/x) + 1/x$, so it is enough to check that this is negative for $x > 1$. An equivalent statement is that $\log(1 - x) + x < 0$ for $0 < x < 1$; this in turn holds because the function $g(x) = \log(1 - x) + x$ tends to 0 as $x \to 0^+$ and has derivative $1 - \frac{1}{1-x} < 0$ for $0 < x < 1$.