Polynomial sum of negligible functions need not be negligible Let $\{\epsilon_i\}_{n \in \mathbb{N}}$ be a sequence of negligible
   functions and $q(n)$ be a polynomial in $n$. Then $f(n) = \sum_{i = 1}^{q(n)} \epsilon_i(n)$ need not be a negligible function.


Ideas

A typical negligible function is $2^{-n}$. Maybe we can expand it to the family $2^{-(n+i)}$ and set $q(n)$ to something that will give a sufficient large sum [didn't work]
Consider the negligible functions
$$\epsilon_i(n) = \begin{cases} 1 &amp; \text{if } n \le i \\ 0 &amp; \text{if } n &gt; i \\ \end{cases}$$

and $q(n) = n$

It should be easy to show that each $\epsilon_i$ function is, in fact, negligible, but the sum $f(n)$ is not...