Limit definition of negligible function

Question

I am reading Dan Boneh's book and I am stuck on Theorem 2.11, whose proof is left as an exercise.

The question is: prove that if $\lim_{n \rightarrow \infty} f(n)n^c = 0$ for all $c > 0$, then $f$ is negligible.

Here, negligible function is defined to be a function $f : \mathbb{Z}_{\geq 1} \rightarrow \mathbb{R}$ such that for any real $c > 0$, there exists an integer $n_0 \geq 1$ such that $f(n) < \frac{1}{n^c}$ for al $n \geq n_0$.

What I've done so far is the following: assume that, for any real $c > 0$, we have $\lim_{n \rightarrow \infty} f(n)n^c = 0$. See that this means that $\lim_{n \rightarrow \infty} f(n)n^{c+1} = 0$ as well. Note that $\frac{1}{n} = \frac{1}{n^{c+1}}n^c$, so $\lim_{n \rightarrow \infty} \frac{1}{n^{c+1}}n^c = \lim_{n \rightarrow \infty} f(n)n^c = 0$, so $f(n)n^c < \frac{1}{n^{c+1}}n^c$ and finally $f(n) < \frac{1}{n^{c+1}}$, as we wanted.

Is this correct? If so, how to justify the part that says $f(n)n^c < \frac{1}{n^{c+1}}n^c$?

Answer 1

Assume that for any $c>0,$ we have $$\lim_{n \rightarrow \infty} f(n)n^{c} = 0.$$ This means that for any $\epsilon>0$ however small, there exists some finite $N$ so that for all $n>N,$ we have $f(n) n^c \leq \epsilon.$ This is the standard $\epsilon$ definition of a limit in analysis (if you go far enough, you are arbitrarily close, i.e., $\epsilon$-close to the limit point, which is here equal to zero).

Note that this directly implies by division that $$ f(n) \leq \frac{\epsilon}{n^c}, \quad \forall n>N $$ as well. Since $\epsilon>0$ was arbitrary we can take it to be in $(0,1)$ and we are done.

Note:

Your assumption was too strong, one need not have $f(n)<1/n,$ for convergence, one can have $f(n)<1/g(n)$ for any growing function $g(n)$ however slowly it may grow. Also, here we can typically assume that $f(n)$ is a positive function, otherwise one may need to use absolute values, but in cryptography the functions are normally positive.