0

I intuitively understand $n^{k} \ll (1 + \epsilon)^n$ however the logic of the proof I don't understand, from the chapter on the hierarchy of standard form functions in the book:

Proof. First set $f(n) = n^k$, $g(n) = (1 + \epsilon)^n$. We compare growth rates:

$$\lim_{n \to \infty} f(n + 1)/f(n) = \lim_{n \to \infty}(1 + n^{−1})^k = 1^k = 1$$

Fix any $c$ (e.g., $c = 1 + \frac{\epsilon}{2}$) with $1 < c < 1 + \epsilon$. There exists $n_0$ so that for $n > n_0$ , $f(n + 1)/f(n) < c$. Hence:

$$\frac{f(n_0 + m)}{g(n_0 + m)} \leq \frac{c^{m}f(n_{0})}{(1 + \epsilon)^{m}g(n_{0})} \to 0$$ as $m \to \infty$.

Question: I understand all the algebra/limits involved, however why does the author compare the limit of $f(n + 1)/f(n)$ in the first place? Unsure of the proof scaffolding reasons for doing this. Also, why $c^{m}$ out of nowhere, we are fixing a constant not an exponential. Where did I misunderstand this?

Gary
  • 31,845
JJbh
  • 3
  • $$ f(n_0 + m) = \frac{{f(n_0 + m)}}{{f(n_0 + m - 1)}}\frac{{f(n_0 + m - 1)}}{{f(n_0 + m - 2)}} \cdots \frac{{f(n_0 + 1)}}{{f(n_0 )}}f(n_0 ) < c^m f(n_0 ). $$ The limit computation was done in order to show that the ratio of consecutive values remains uniformly bounded by a positive constant $c$ arbitrarily close to $1$ if the argument is large enough. – Gary Nov 30 '21 at 00:56
  • @Gary thanks for explanation – JJbh Nov 30 '21 at 01:12

1 Answers1

1

Welcome to MSE!

The idea is to look at how quickly $f$ grows as a function of $n$. One way to do this is to look at the ratio $f(n+1)/f(n)$, since then we'll have (for instance)

$$f(n+3) = \frac{f(n+3)}{f(n+2)} \frac{f(n+2)}{f(n+1)} \frac{f(n+1)}{f(n)} f(n)$$

and if each $\frac{f(n+k+1)}{f(n+k)} \approx c$, then we see $f(n+3) \approx c^3 f(n)$ by applying this estimate to the above expression.

For us, then, we know that $\lim_{n \to \infty} \frac{f(n+1)}{f(n)} = 1$, and since it's clear that $f(n+1) > f(n)$ is always true, we know that we're approaching $1$ from above. Expanding the definition of limit, we learn that for every $\delta > 0$, (say, $\delta = \epsilon / 2$), we can find an $N$ big enough so that

$$1 < \frac{f(n+1)}{f(n)} < 1+\delta$$

whenever $n \geq N$.

This means we can approximate $f(N+k) < (1 + \delta)^k f(N)$, which is much simpler to deal with. In particular, we see

$$ \frac{f(N+k)}{g(N+k)} = \frac{(1 + \epsilon/2)^k f(N)}{(1 + \epsilon)^k g(N)} \to 0 $$

Now, I agree that this is kind of pulled out of a hat, but it's a very common trick: In general when trying to consider how a function $f$ grows, looking at the ratio of terms $f(n+1)/f(n)$ is a useful idea. See also the proof of the Cauchy-Hadamard Theorem, for instance.

It's worth keeping this in your back pocket for future problems!

I hope this helps ^_^

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87