Negligible function arithmetics

Question

By definition of negligible function, if $q(n)$ is a negligible function, does $poly(n)*q(n)$ is also a negligible function? How can I prove it?

Answer 1

Yes, it is also a negligible function. First you have to find a power of $n$ that is eventually greater than $poly(n)$. You can do this, just take a power higher than the highest power in $poly(n)$ Let it be $n^k$ and $n^k \gt poly(n)$ whenever $n \gt N_1$

Now if somebody gives us a $c$, we have to find an $N_c$ such that $poly(n)q(n) \lt \frac 1{n^c}$ whenever $n \gt N_c$. Because $q(n)$ is negligible, we can find an $N_q$ such that $q(n) \lt \frac 1{n^{c+k}}$. Then we can take $N_c=\max (N_1,N_q)$ and $poly(n)q(n)\lt n^kq(n) \lt n^k\frac 1{n^{c+k}}=\frac 1{x^c}$