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.

  • 12
    $\begingroup$ 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. $\endgroup$ – t.b. Dec 12 '11 at 6:10
  • $\begingroup$ See also math.stackexchange.com/questions/64860 with some other proofs $\endgroup$ – 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.

  • 1
    $\begingroup$ Wonderful! Thank you, Mike. Have some points! $\endgroup$ – Bruno Joyal Jan 6 '12 at 19:22
  • 1
    $\begingroup$ You're quite welcome, thanks for asking this nice question! $\endgroup$ – 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$).

  • 3
    $\begingroup$ Do you mean $(1+x)^n \ge 1+nx$? $\endgroup$ – 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$.

  • 2
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Dec 12 '11 at 20:30
  • $\begingroup$ @BrianM.Scott: yeah you're right. Can it be salvaged? $\endgroup$ – Greg Martin Dec 13 '11 at 1:40
  • $\begingroup$ I’ve been tinkering, but so far without much luck. $\endgroup$ – Brian M. Scott Dec 13 '11 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.