Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
12  
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

3 Answers 3

up vote 24 down vote accepted

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.

share|improve this answer
1  
Wonderful! Thank you, Mike. Have some points! –  Bruno Joyal Jan 6 '12 at 19:22
1  
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$).

share|improve this answer
3  
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$.

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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