\problemdata      
        {asymptotics-4} % latex-friendly label for the prob.
        {Asymptotics} % The topic(s) of the problem content.
        {F00 Tu7} % Source (if known)
        {S02 CP6F} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).



\begin{problem}
Prove or give a counterexample:
If $f_1,f_2,\dots$ is a sequence of functions from $\naturals$ to
$\naturals$ such that $f_i(n) = O(1)$ for all $i\geq 1$, then 
\[
\sum_{i=1}^n f_i(n) = O(2^n).
\]

\solution{
False.  For a counterexample, pick $f_i$ to be the constant function 
\[
\text{for all $n$}:\quad f_i(n) = 4^i, 
\]
for all $i\geq 1$.  Then clearly for each $i$, we have $f_i = O(1)$.  But
\[
\sum_{i=1}^n f_i(n) \geq f_n(n) = 4^n,
\]
which is not $O(2^n)$.
}
\end{problem} 

