How can I solve this?

I'm trying to prove using limits but it's not working..


  • 1
    $\begingroup$ have you tried to use the logarithm? in fact above is true because $n$ grows faster than $\log(n)$ $\endgroup$
    – user190080
    Jul 10 '15 at 13:36
  • $\begingroup$ Yes, I tried to use the logarithm in the ratio limit but i got 1 and not 0. Am I doing something wrong? $\endgroup$
    – Leandro
    Jul 10 '15 at 13:39
  • 2
    $\begingroup$ What did you try exactly? We can't tell what you did wrong without seeing what you did. $\endgroup$ Jul 10 '15 at 13:44
  • $\begingroup$ I tried apply logarithm in the ratio= limt n-> inf [log n^a/ log a^n] $\endgroup$
    – Leandro
    Jul 10 '15 at 13:46
  • $\begingroup$ Okay. And can you transform $\dfrac{\log (n^a)}{\log (a^n)}$ into a form that may be easier to handle? $\endgroup$ Jul 10 '15 at 13:49

so start with for $a>1$ and $\forall n$ big enough we have
$$n^a < a^n \Leftrightarrow \log(n^a)<\log(a^n)\Leftrightarrow a\log(n)<n\log(a)\Leftrightarrow 1<\frac{\log(a)}{a}\frac{n}{\log(n)} $$ and we fixed $a$, so $\frac{\log(a)}{a}=c>0$ is just a constant.

So in fact we have to show, that $$ 1<c\frac{n}{\log(n)} $$ holds for all constants $c>0$ and for all $n\ge n_0(c)$. But this is ofcourse true, since $$ \lim_{n\rightarrow\infty}\frac{n}{\log(n)}=\infty \text{ if we consider }\bar{\mathbb{R}}:=\mathbb{R}\cup\{-\infty,+\infty\} $$ so it grows above each bound.



Let $x_{n} = a^{n}/n^{a}$ and then we have $$\frac{x_{n + 1}}{x_{n}} = \frac{a^{n + 1}}{(n + 1)^{a}}\cdot\frac{n^{a}}{a^{n}} = a\left(\frac{n}{n + 1}\right)^{a} \to a \text{ as } n \to \infty$$ Now $a > 1$ and hence we can choose a number $k$ with $1 < k < a$ and by the above limit there exists a positive integer $m$ such that $$\frac{x_{n + 1}}{x_{n}} > k$$ for all $n \geq m$. Thus we can see that $$\frac{x_{m + n}}{x_{m}} > k^{n} $$ for all positive integers $n$. Now we can see that $k > 1$ and hence $$k^{n} = (1 + (k - 1))^{n} \geq 1 + n(k - 1) $$ so that $k^{n} \to \infty$ as $n \to \infty$. It follows that $x_{m + n} > x_{m}k^{n}$ and hence $x_{m + n} \to \infty$ as $n \to \infty$. Thus $x_{n} \to \infty$ as $n \to \infty$.

It is now obvious that after a certain value of $n$ we will always have $x_{n} > 1$ and hence $a^{n} > n^{a}$ after a certain value of $n$. There is no need to go for logarithms and complicated limits related to them. Just simple limits coupled with definition of limit is sufficient to handle the problem.


My attempt at an inductive proof:

Base Case: $n=1 \Rightarrow a^1 > 1$ Which is true by the initial condition

Assumption: $a^k > k^a$

Want to show: $a^{k+1} > (k+1)^a$

Multiply both sides of the assumption by $a$ to get: $a^{k+1} > ak^a$

Thus, it suffices to show that $ak^a > (k+1)^a$

Dividing both sides by the RHS gives: $a(\frac{k}{k+1})^a >1$

For $k$ large enough, the limit of $\frac{k}{k+1}$ is 1, so for sufficiently large $k$ the inequality reduces to $a>1$, which is true

I'm not sure if this is actually correct: can we consider a limit within an inductive proof? If not, is there another way we can finish the proof off?


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.