# Proving that one quantity *eventually* surpasses the other

I want to prove the following; $$\forall t>0\ \ \forall m\in \mathbb{N} \ \ \exists N \in \mathbb{N} \ \ \forall n\geq N: \ (1+t)^n > n^m.$$

For readers who hate quantifiers, here's the version in words: "$(1+t)^n$ eventually surpasses $n^m$ for some $t>0$ and $m\in \mathbb{N}$".

Though this sounds simple enough, I couldn't manage to prove it using only very elementary statements about the real numbers, like the archimedian property etc. (so no derivates and so on involved).

My questions are:

1) Is there a simple (as described above) proof for this ? (If there isn't, I would also be happy with a proof using more of the analysis machinery.)

2) Is there a way to express the least $N$, which satisfies the above, in a closed form ?

3) I have somewhere heard of a theorem, that two real convex functions can have at most two intersection points (and the above statement seems closely related to this theorem), so I would be very happy, if someone could also give me a reference for this theorem.

-
3) is false. $e^x = (x+5)^2$ has 3 solutions. A pair of functions with any number of intersections could be constructed. –  Karolis Juodelė Sep 1 '12 at 17:44

1) Yes. The inequality is equivalent to $((1+t)^{\frac{1}{m}})^n>n$ by taking the $\frac{1}{m}$th power of both sides which reduces to your original problem to the problem with $m=1$ since $(1+t)^{\frac{1}{m}}$ is of the form $1+u$ with $u$ a strictly positive real.

So we'll assume $m=1$. We can expand $(1+t)^n$ using the binomial theorem as (assuming $n>2$)

$$(1+t)^n=1+nt+\frac{n(n-1)}{2}t^2+...$$

So in particular we get $(1+t)^n>1+\frac{n(n-1)}{2}t^2$ if $n>2$, so if we pick $N$ such that $\frac{N-1}{2}t^2>1$ and $N>2$ (which we can do by the Archimedean property), we find that $(1+t)^n>n$ for all $n\geq N$.

2) The Lambert W function should be able to do that, yes.

-
I would almost accept your answer; could you help me out with 3) ? –  temo Sep 1 '12 at 17:34
ok, has been answered now by Juodele and Hagen –  temo Sep 1 '12 at 17:47

(1) Show $2^n > n$ for all $n$ immediately by induction.

(2) Moreover, given $c$ clearly $2^n> c$ for almost all $n$.

Lemma: For $c>0$ and $m\in \mathbb N$, we have $2^n > c n^m$ for almost all $n$.

Proof by induction on $m$. The case $m=0$ is just (2). Assume the statement is true for some $m$. We want to show that $2^n> c n^{m+1}$ for almost all $n$. By induction assumption, there is $N$ such that $k>N$ implies $2^k>2^{m+2} c k^m$. If $n>2N$ is even, write $n=2k$ with $k>N$. Then $2^n = 2^k\cdot 2^k>2^{m+2}c k^m\cdot k = 2c\cdot (2k)^{m+1} > c n^{m+1}$ (we use (1) in this). If $n>2N$ is odd, write $n=2k-1$ with $k>N$. Then $2^n = \frac12\cdot2^{2k}>c\cdot (2k)^{m+1}>c n^{m+1}$. \qed

Finally, to change the base from 2 to $1+t$, select $r\ge\frac 1t$. Then $(1+t)^r \ge 1+r t \ge 2$. Hence if $n=k r - s$ with $0\le s < r$, then $(1+t)^n>\frac12 2^k> \frac12\cdot(2r^m) k^m=(rk)^m\ge n^m$ for almost all $n$.

--

$x\mapsto x^4$ and $x\mapsto x^2$ are convex, but $x^4-x^2=0$ has three solutions $-1, 0$,and $1$.