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