Monday, May 28, 2018

real analysis - How to prove that exponential grows faster than polynomial?



In other words, how to prove:





For all real constants $a$ and $b$ such that $a > 1$,



$$\lim_{n\rightarrow\infty}\frac{n^b}{a^n} = 0$$




I know the definition of limit but I feel that it's not enough to prove this theorem.


Answer



We could prove this by induction on integers $k$:




$$
\lim_{n \to \infty} \frac{n^k}{a^n} = 0.
$$



The case $k = 0$ is straightforward. I will leave the induction step to you. To see how this implies the statement for all real $b$, just note that every real number is less than some integer. In particular, $b \leq \lceil b \rceil$. Thus,



$$
0 \leq \lim_{n \to \infty} \frac{n^b}{a^n} \leq \lim_{n \to \infty} \frac{n^{\lceil b \rceil}}{a^n} = 0.
$$




The first inequality follows since all the terms are positive. The last equality follows from the induction we established previously.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...