Prove for any $a>1$ there exist a natural number, $N$, such that $a^n>n$ for all $n \ge N$

Prove for any $a>1$ there exist a natural number, $N$, such that $a^n>n$ for all $n \ge N$

My attempt:

By definition, for $N$ to be a natural number $1\le N \le ∞$ for any integer $N$.

By induction, the base case $n=1$ is true because $a^1>1$ which is true.

Now assume that $a^k>k$ is true, then it is also true for $n= k+1$.

Hypothesis

$a^{k+1}>k+1$

Now I am not sure if I am on the right track

Let $x = a-1 > 0$ (by hypothesis). $a^n = (1+x)^n > \dfrac{n(n-1)}{2} x^2$ for $n \ge 2$ by the binomial theorem, and the last term is $\ge n$ if $\frac {n-1} {2} x^2 \ge 1$. So if $n \ge 1 + \dfrac{2}{x^2}$ (which also automatically makes $n \ge 2$), you have $a^n > n$.

• This solution is better than mine. – student forever Apr 12 '16 at 1:21

Since $$\lim_{x \to \infty} \frac{a^x}{x} =\infty,$$ there is an $N>0$ such that for all $n>N$ we will have $$\frac{a^n}{n}>1.$$

• Why is the limit infinity? How would you prove that without being circular? – астон вілла олоф мэллбэрг Apr 12 '16 at 1:01
• Using L'hopital. I wrote $x$ istead of $n$ in order to use L'hopital. – student forever Apr 12 '16 at 1:02
• Oh I see. Nice one.+1 – астон вілла олоф мэллбэрг Apr 12 '16 at 1:02
• How does the first part imply the second? – Ben Apr 12 '16 at 1:11
• It goes to infinity, this means it is bigger than for any reel number $M$ after for some $N$. We can choose $M=1$. – student forever Apr 12 '16 at 1:19

More is true:

For any $a > 1$ and $k > 1$ there is a $n(a, k)$ such that $n > n(a, k) \implies a^n > n^k$.

Proof:

$a^n = e^{n \ln(a)} \gt \dfrac{(n \ln(a))^m}{m!}$ for all $m$ (from the power series for $e^x$).

We want to make $\dfrac{(n \ln(a))^m}{m!} \gt n^k$. If we choose $m = k+1$, this is $\dfrac{(n \ln(a))^{k+1}}{(k+1)!} \gt n^k$ or $n > \dfrac{(k+1)!}{\ln(a)^{k+1}}$.

By choosing $m$ larger compared with $k$ we can get a smaller bound for $n$, but this is enough.

• This, too, can be proved without calculus, using just elementary algebra (the binomial theorem), as shown in my answer. The general idea is the same - just use the $x^{k+1}$ term in the binomial expansion. Problems like the one asked by the OP should not use much more advanced tools than the problem itself. – mathguy Apr 12 '16 at 2:21