0
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

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

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mathguy Apr 12 '16 at 2:21

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.