36
$\begingroup$

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.

  • 0
    See also http://math.stackexchange.com/questions/64860/ with some other proofs2011-12-26

3 Answers 3

27

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
    You're quite welcome, thanks for asking this nice question!2012-01-10
3

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
    Do you mean $(1+x)^n \ge 1+nx$?2011-12-14
0

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

  • 0
    I’ve been tinkering, but so far without much luck.2011-12-13