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

-
In case there's such a combinatorial proof, I'd be curious to know if there's a similar argument for the fact that $$\left(n+1\right)^{2n+3} \gt n^{n+1} \left(n+2\right)^{n+2},$$ that is: $\left(1+\frac{1}{n}\right)^{n+1}$ is decreasing. – t.b. Dec 12 '11 at 6:10
See also math.stackexchange.com/questions/64860 with some other proofs – sdcvvc Dec 26 '11 at 23:21

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.

-
Wonderful! Thank you, Mike. Have some points! – Bruno Joyal Jan 6 '12 at 19:22
You're quite welcome, thanks for asking this nice question! – Mike F Jan 10 '12 at 7:24

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

-
Do you mean $(1+x)^n \ge 1+nx$? – robjohn Dec 14 '11 at 18:07

I think the following function $\Phi \colon S_{n,n} \times S_{n,n+2} \times S_{1,n+2} \to S_{n,n+1} \times S_{n,n+1} \times S_{1,n+1}$ is a surjection, which would prove the desired inequality. Each element of the domain and the range of $\Phi$ is a function on $\{1,\dots,n\} \cup \{1,\dots,n\} \cup \{1\}$; for the sake of our sanity let's write this as $\{1_a,\dots,n_a\} \cup \{1_b,\dots,n_b\} \cup \{1_c\}$.

Given $f\in S_{n,n} \times S_{n,n+2} \times S_{1,n+2}$, we define $\Phi(f) \in S_{n,n+1} \times S_{n,n+1} \times S_{1,n+1}$ as follows. (Hereafter, $j$ always denotes an integer between $1$ and $n$.)

• If $f(1_c) \ne n+2$, then set:
• $\Phi(f)(j_a) = \begin{cases} f(j_a), & \text{if } f(j_b) \ne n+2, \\ n+1, & \text{if } f(j_b) = n+2. \end{cases}$
• $\Phi(f)(j_b) = \begin{cases} f(j_b), & \text{if } f(j_b) \ne n+2, \\ f(j_a), & \text{if } f(j_b) = n+2. \end{cases}$
• $\Phi(f)(1_c) = f(1_c)$.
• If $f(1_c) = n+2$ and there exists $1\le j\le n$ such that $f(j_b) \ge n+1$, then let $k$ be the least such $j$; then set:
• $\Phi(f)(j_a) = \begin{cases} f(j_a), & \text{if } f(j_b) \le n, \\ n+1, & \text{if } f(j_b) \ge n+1. \end{cases}$
• $\Phi(f)(j_b) = \begin{cases} f(j_b), & \text{if } f(j_b) \le n, \\ n+1, & \text{if } f(j_b) \ge n+1. \end{cases}$
• $\Phi(f)(1_c) = \begin{cases} f(k_a), & \text{if } f(k_b) = n+1, \\ f(k_a)+1, & \text{if } f(k_b) = n+2. \end{cases}$
• If $f(1_c) = n+2$ but there does not exist $1\le j\le n$ such that $f(j_b) \ge n+1$, then I don't care what $\Phi(f)$ is.

The first part of the construction covers every function $g \in S_{n,n+1} \times S_{n,n+1} \times S_{1,n+1}$ except those for which there exists $j$ such that $g(j_a) = g(j_b) = n+1$; the second part (hopefully) covers these special functions $g$.

-
This doesn’t quite work. If $n=2$, it doesn’t cover $$g(1_a)=g(1_b)=g(2_b)=3,g(2_a)=g(1_c)=1\;.$$ $g(1_a)=g(1_b)=3$ puts it in the second part of the construction, where $g(2_a)<g(2_b)=3$ is impossible. – Brian M. Scott Dec 12 '11 at 20:30
@BrianM.Scott: yeah you're right. Can it be salvaged? – Greg Martin Dec 13 '11 at 1:40
I’ve been tinkering, but so far without much luck. – Brian M. Scott Dec 13 '11 at 7:29