A combinatorial proof of $n^n(n+2)^{n+1}>(n+1)^{2n+1}$?

The statement is simply that the sequence $\left(1+\frac{1}{n}\right)^n$ is increasing.

Since the numbers $n^m$ have quite natural combinatorial interpretations, it makes me wonder if a combinatorial proof exists, but I haven't been able to find one.

For example, if we let $S_{n,m}$ denote the set of function $\{1, \dots, n\} \to \{1, \dots, m\}$, then a proof would follow from the construction of an injection $S_{2n+1,n+1} \hookrightarrow S_{n, n} \times S_{n+1,n+2} $, or of a surjection going the other way.

Solution 1:

I managed to come up with a combinatorial proof of the statement in t.b.'s comment. I would guess a similar argument solves the original problem. Anyway, let $n$ be a positive integer. We will prove that $$ n^{2n+1} > (n-1)^n(n+1)^{n+1}.$$ After multiplying by through by $n$ and performing some trivial (though slightly arcane) manipulations, we see this is equivalent to proving $$(n^2)^{n+1} > (n^2-1)^{n+1} + (n+1) \cdot (n^2-1)^n.$$ Now for the combinatorics (see problem statement for notation). The LHS counts the functions in $S_{n+1,n^2}$. The RHS counts only the functions in $S_{n+1,n^2}$ which do not take the value $1$ (via the first term) or else take the value $1$ exactly once (via the second term). And, well, that's it!!

Added: Okay I think I figured out how to do the original problem in the same sort of way. The combinatorial step is a bit clumsier for some reason. Maybe someone else can see a better way? As before, let $n$ be a positive integer. We will prove that $$(n-1)^{n-1}(n+1)^n > n^{2n-1}.$$ Multiplying through by $n-1$, this becomes $$(n^2 -1)^n > (n^2)^n - n \cdot (n^2)^{n-1}$$ or, equivalently, $$(n^2 -1)^n + n \cdot (n^2)^{n-1} > (n^2)^n.$$ This last bound can be proven combinatorially. On the RHS we have all the functions in $S_{n,n^2}$. The first term on the LHS counts the functions in $S_{n,n^2}$ which never take the value $1$. Let $S$ be the set of functions in $S_{n,n^2}$ which do take the value $1$. We need to prove $S$ has less than $n \cdot (n^2)^{n-1}$ elements. We can inject $S$ into $\{1,\ldots,n\} \times S_{n-1,n^2}$ by sending $f \in S$ to the pair $(x,f_x)$ where $x$ is the smallest member of $\{1,\ldots,n\}$ with $f(x) = 1$, and $f_x$ is obtained from $f$ by "skipping" over $x$ (in order to get a function with one less element in the domain). In order to see the inequality is strict, note that (I think maybe assuming $n \geq 2$) $(n,1)$ is not in the range of this injection (here $1$ is the constant function). This completes the proof.

Solution 2:

This isn't combinatorial, but my favorite proof is from N.S Mendelsohn, "An application of a famous inequality", Amer. Math. Monthly 58 (1951), 563.

The proof use the arithmetic-geometric mean inequality (AGMI) in the form $(\frac{1}{n}\sum_{i=1}^n a_i)^n \ge \prod_{i=1}^n a_i $ with the inequality being strict if not all the $a_i$ are equal.

Consider $n$ values of $1+1/n$ and 1 value of 1. By the AGMI, $((n+2)/(n+1))^{n+1} > (1+1/n)^n$, or $(1+1/(n+1))^{n+1} > (1+1/n)^n$.

Consider $n$ values of $1-1/n$ and 1 value of 1. By the AGMI, $(n/(n+1))^{n+1} > (1-1/n)^n$ or $(1+1/n)^{n+1} < (1+1/(n-1))^n$.

An interesting note is that this uses the version of the AGMI in which $n-1$ of the $n$ values are the same, which can be shown to be implied by Bernoulli's inequality ($(1+x)^n \ge 1+nx$ for $x \ge 0$ and integer $n \ge 1$).