# Proof of a little-oh growth function.

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!

-
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

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

-
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

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

-