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.

Prove that $n^{2.5} \in o(1.1^{n})$.

Prove using limits. That: $$\lim_{n\to\infty} \left(\frac{f(x)}{g(x)}\right) = 0$$

Thanks!

share|improve this question
    
Welcome to MSE! It is helpful to share with us your thoughts and what you have tried on the problem. Regards –  Amzoti Apr 15 '13 at 18:22
add comment

2 Answers

up vote 0 down vote accepted

We want to show that $\lim_{x\to\infty}\frac{x^{2.5}}{(1.1)^x}=0$. There are many ways to do this. One can use L'Hospital's Rule, for example.

It is less messy to use L'Hospital's Rule $3$ times, and prove the stronger result with $x^3$ on top instead of $x^{2.5}$. For differentiating the bottom, note that $(1.1)^x=e^{\ln 1.1)x}$.

We can also disobey the instructions about $x$. Note that by the Binomial Theorem, $$(1.1)^n=1+\binom{n}{1}(0.1)+\binom{n}{2}(0.1)^2+\binom{n}{3}(0.1)^3+\cdots.$$ In particular, if $n\gt 3$, we have $$(1.1)^n \gt \binom{n}{3}(0.1)^3.$$

The right side above is a cubic in $n$. An easy argument shows that $$\lim_{n\to\infty}\frac{n^{2.5}}{\binom{n}{3}}=0.$$

share|improve this answer
    
Thanks! How would you take the derivative of (1.1)^x 3 times? or well 2 more times after your first. –  user1201359 Apr 15 '13 at 19:13
    
As mentioned, $(1.1)^x=e^{cx}$ where $c=\ln(1.1)$. The derivative is $ce^{cx}$, the second derivative is $c^2e^{cx}$, the third derivative is $c^3e^{cx}$. –  André Nicolas Apr 15 '13 at 19:16
    
Great, thank you! :) –  user1201359 Apr 15 '13 at 19:22
    
You are welcome. There are many other ways to handle the problem. Basically, the reason the limit is $0$ is that in the long run an exponential grows far faster than any polynomial. But that might be too imprecise for the grader! It is, however, the right way to view the matter. –  André Nicolas Apr 15 '13 at 19:31
add comment

You want to show $$\lim_{n\to\infty} \frac{n^{2.5}}{1.1^n} = 0$$

There are lots of ways of showing this limit. In fact, it's much more general. $$\lim_{n\to\infty} \frac{n^{k}}{\alpha^n} = 0$$ for any number $k$, and $\alpha>1$.


A simple way to do it might be to look at the ratio of two terms in this sequence. $$\frac{(n+1)^k/\alpha^{n+1}}{n^k/\alpha^n} = \left(1+\frac{1}{n}\right)^k\times\frac{1}{\alpha} \to \frac{1}{\alpha}<1 \quad \text{as }n\to\infty$$

So since we're multiplying infinitely many things less than 1 together, we tend towards 0.


Instead, you might write $$\alpha^n = \exp(n \log \alpha)$$ so you want $$\lim_{n\to\infty} n^{k}e^{-n \log \alpha} = 0$$ which holds because $\log \alpha > 0$, and exponentials always win against polynomials. (Since $\exp n = 1 + \cdots + n^{100}/100! + \cdots$.)

Or you might go a bit further and write it as $$\lim_{n\to\infty} e^{k\log n-n \log \alpha} = 0$$ and use the fact that $n$ grows much faster than $\log n$.

share|improve this answer
add comment

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.