Tuesday, November 13, 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...