%typo {b^2}^y ==> (b^2)^y 3/15/98
\documentstyle[11pt,twoside,amsfonts,amstex,psfig]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{rec#1}{Notes for Recitation #1 (#2/98)}{#3}
}


\begin{document}

\recn{5}{3/6}{March 7, 1998}


\iffalse
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi

\section{Asymptotic Notations}

There is need to compare growth rates of functions in many parts of
Mathematics and Computer Science, and there are about a half-dozen
standard ways to make such comparisons.  For the time being, we'll stick
to $O()$, $\Theta()$, and $\Omega()$ which were introduced in lecture:

\begin{defin}
For functions $f,g:\reals\to\reals$,  define
\[f=O(g) \mbox{  iff  } \exists c>0 \exists x_0 \forall x \geq x_0: |f(x)| \leq
cg(x).\]
Also
\[f=\Theta(g) \mbox{  iff  } [f=O(g) \mbox{ and } g = O(f)],\]
and
\[f=\Omega(g) \mbox{  iff  } g = O(f).\]
\end{defin}

The value of these notations is that they highlight growth rate and allow
suppression of distracting factors and low-order terms.  For example, if
the running time of an algorithm is
\[T(n) = 10n^3 - 20n^2 + 1,\]
then
\[T(n) = \Theta(n^3).\]
$T(n)$ grows \emph{cubically}: it is bounded both above and below by
functions of the form $c n^3$.

Another such example is
\[{{\pi^23^{x-7} + {(2.7x^{113} + x^9- 86)^4 \over \sqrt{x}} - 1.08^{3x}}} =
\Theta(3^x).\]

\begin{lemma}\label{abO}
If $f = O(g)$, then $af = O(bg)$ for any $a,b>0$
\end{lemma}

\emph{Exercise}: Prove Lemma~\ref{abO}.
\medskip

If $l(x)$ is any function which increases unboundedly --- $\ln x$ is a
good example --- then $x/{l(x)} < x$ as soon as $x$ gets large enough that
$l(x) > 1$.  In particular, $x/{l(x)} = O(x)$.  Intuitively, $f = O(g)$
means that, to within a constant factor, $g$ grows at least as fast as
$f$.  In this case, the $g$ grows strictly faster:

\begin{theorem}\label{xlnx}
\[\mbox{It is not true that } x = O(x/\ln x).\]
\end{theorem}

\begin{proof}
We must show that for all $c > 0$, there does not exist an $x_0$
such that for all $x \geq x_0$, we have $|x| \leq c x/\ln x$.  But
$x > c x/\ln x$ for all $x > e^c$, so there can't be such an $x_0$.
\end{proof}

Notice that, again, the only fact we used about $\ln x$ in the above proof
is that it is an unbounded increasing function.

A more significant fact about the growth of $\ln x$ is
\begin{theorem}\label{lno}
\[\forall a > 0: \ln x = O(x^a).\]
\end{theorem}

\begin{proof}
Remember L'H$\hat{\mbox{o}}$pital's rule:  if $\mbox{Lim}_{x\rightarrow \infty}
f(x) = \infty = \mbox{Lim}_{x\rightarrow \infty} g(x)$, then
\[\mbox{Lim}_{x\rightarrow \infty} {f(x) / g(x)} = \mbox{Lim}_{x\rightarrow \infty}
{f'(x)/ g'(x)}\]
where $f',g'$ are the derivatives of $f,g$, and $f, g, f', g'$ are
continuous.
So
\[\mbox{Lim}_{x\rightarrow \infty} {\ln x \over x^a} =  
\mbox{Lim}_{x\rightarrow \infty} {{1/x} \over {a x^{a-1}}} = \mbox{Lim}_{x\rightarrow
\infty} {1 \over {a x^a}} = 0.\] The last equality follow from the
familiar fact -- which we'll take for granted -- that that for all $a>0$,
the value of $x^a$ grows unboundedly as $x$ approaches infinity.  Since
the limit is 0, we can be sure that once $x$ is large enough, $\ln x/x^a
\leq 1$, that is $\ln x \leq x^a$.  So indeed $\ln x = O(x^a)$.
\end{proof}

Similarly,
\begin{theorem}\label{expo}
\[\forall a >1: x = O(a^x).\]
\end{theorem}
\begin{proof}
We know that $\ln a > 0$, so in the Taylor series
\[a^x = a^0 + x (\ln a)a^0 + x^2 (\ln a)^2a^0/2 + \dots\]
all the coefficients are positive.  Hence
\[a^x > 1 + (\ln a)x > (\ln a)x \mbox{ for }x>0.\]
\end{proof}

\subsection*{Asymptotics of Powers and Exponentials}

We include here notes on a few more basic facts about growth of powers and
exponentials which were not presented recitation.

\begin{corollary}\label{expk}
\[\forall k\in \naturals, a >1: y^k = O(a^y).\]
\end{corollary}
\begin{proof}
By induction on $k$.  In the base case $k=0$, we have $y^k = y^0 = 1 < a
\leq a^y$ for $y\geq 1$, so $y^0 = O(a^y)$.  Notice that the only facts we
have used here about $a^y$ are that $a^1 = a$ and $a^y$ is a nondecreasing
function of $y$.

We now assume the induction hypothesis $y^k = O(b^y)$ for all $b>1$ and
prove $y^{k+1} = O(a^y)$ for all $a>1$.  For any $a > 1$, let
$b=\sqrt{a}$, so also $b > 1$.  By hypothesis, $y^k
\leq cb^y$ for some $c>0$ and all $y \geq$ some $y_0$.  Also, by
Theorem~\ref{expo}, $y \leq c'b^y$ for some $c'>0$ and all $y \geq$ some
$y'_0$.  So 
\[\begin{array}{lclclcl}
y^{k+1}& = & y(y^k) & \leq & c'b^y(cb^y) & = & cc'(b^y)^2\\
& = & cc'b^{2y} & = & cc'(b^2)^y & = & cc'a^y
\end{array}\]
for $y\geq \max(y_0, y'_0)$, which shows that $y^{k+1} = O(a^y)$.
\end{proof}

Theorems~\ref{lno} and~\ref{expo} are important enough that it's worth
examining another way to prove them.  This time, we'll do it without
appeal to calculus, starting with:

\begin{lemma}\label{lnln}
If $\mbox{Lim}_{x\rightarrow \infty} g(x) = \infty$ and $f = O(g)$, then
$\ln f = O(\ln g)$.
\end{lemma}
\begin{proof}
Since $f = O(g)$, there are $c>0$ and $x_0$ such that $f(x) \leq cg(x)$
for all $x\geq x_0$.  Since $g(x)$ goes to $\infty$ with $x$, so does $\ln
g(x)$ and in particular, $\ln g(x)\geq 1$ for all $x > $ some $x_1$.
So for $x\geq \max(x_0, x_1)$,
\[\ln f(x)  \leq  \ln cg(x) = \ln c + \ln g(x) \leq  (\ln c + 1)\ln g(x),\]
and hence $\ln f(x) = O(\ln g(x))$.
\end{proof}

We'll prove Theorem~\ref{lno} by showing that it follows from
Corollary~\ref{expk} and Lemma~\ref{lnln}.  To see this, for $a>0$, let $k
= \ceil{1/a}$.  From Theorem~\ref{expk}, we have $y^k = O(e^y)$.  If we
change variables, letting $x = y^k$, then it follows from the definition
of $O()$ that $x = O(e^{x^{1/k}})$.  Since $1/k \leq a$, also $x^{1/k}
\leq x^a$, so $x=O(e^{x^a})$.  Now by Lemma~\ref{lnln}, $\ln x = O(x^a)$.

Since Corollary~\ref{expk} followed from Theorem~\ref{expo}, all that's
left to show is a noncalculus proof of Theorem~\ref{expo}.  We'll again
use the fact that $a^x$ is nondecreasing, which implies that if
$n=\floor{x}$, then $a^n \leq a^x$.  Since $x = O(\floor{x})$,
Theorem~\ref{expo} will follow if we prove
\[\forall a>1: n = O(a^n)\]
where $n$ is a variable ranging over $\naturals$.  But this follows
immediately from:
\begin{lemma}
For all $\epsilon >0$ and $n\in \naturals$,
\[n\epsilon \leq (1 + \epsilon)^n.\]
\end{lemma}
\begin{proof}
We will prove by induction the stronger fact that
\[1 + n\epsilon \leq (1 + \epsilon)^n.\]

The base case $n=0$ is immediate.

So suppose $1 + n\epsilon \leq (1 + \epsilon)^n$.  Multiplying both sides
of this inequality by $1+\epsilon$ yields
\[(1+\epsilon)(1 + n\epsilon) \leq (1 + \epsilon)^{n+1}\]
But
\[(1+\epsilon)(1 + n\epsilon) = 1 + (n+1)\epsilon + n\epsilon^2 \geq
1 + (n+1)\epsilon,\]
so
\[1 + (n+1)\epsilon \leq (1 + \epsilon)^{n+1}.\]
\end{proof}


A final note about asymptotic notation.  Often one sees expressions
like:
\[(1 + 1/x)^n = 1 + n/x + O(1/x^2).\]
The above expression really means that 
\[(1 + 1/x)^n - 1 - n/x = O(1/x^2).\]
That is, the error term in the approximation for $(1+1/x)^n$ is at most a
constant divided by $x^2$.

\iffalse

One has to be careful when combining inductive proofs with aysmptotic
notation.  Here is another example of a wrong proof.  Recall that
$F_n$ denotes the $n$-th Fibonacci number.

\begin{falsethm}
$F_n = O(1)$
\end{falsethm}

{\em Proof. } The proof is by strong induction.  Let $P(n)$ be the
predicate that $F_n = O(1)$.  In the base case, $P(1)$ is true because
$F_1 = 1 = O(1)$.  In the inductive step, for $n \geq 1$ assume that
$F_1 = O(1), F_2 = O(1), ldots, F_n = O(1)$ to prove that $F_{n+1} =
O(1)$.  There are two cases.  If $n = 1$, then $F_{n+1} = F_2 = 1 =
O(1)$.  If $n > 1$, then $F_{n+1} = F_n + F_{n-1} = O(1) + O(1) =
O(1).$ \qed

Where is the bug?!  The proof is actually correct; the problem is that
it is not a proof of the theorem!  What we actually proved is that
$\forall n: F_n = O(1)$.  It is in fact the case that $\forall n:
P(n)$ i.e. $\forall n: F_n = O(1)$ is true. This is because once we
fix $n$, i.e. within the quantifier, $F_n$ is just a specific number
such as $F_{100}$ or $F_{1000}$ etc. so it is a constant and hence we
can say it is $O(1)$. However, this does not imply the same about the
{\em function} $f(n) = F_n$ which is what we care about.

\fi

\iffalse
\begin{claim}
$x\ln x = O(x^{1.1})$
\end{claim}
\begin{proof}

Let $x_0 = e^{10}, c=1$. Then $\forall x \geq x_0: \ln x \leq \ln x^{0.1}$.

Hence $\forall x \geq x_0: x\log_2 x \leq x^{1.1}$, i.e., $x\ln x = O(x^{1.1})$.

\end{proof}

Can we make a stronger statement?  In this case we can actually
say that $x \log x = o(x^{1.1})$. Roughly speaking, $f(x) = o(g(x))$
means that $f$ grows slower than $g$ as $x$ increases. 
Our definition from class says:

$f(x) = o(g(x))$ if $\forall c > 0, \exists x_0$ such that $\forall x \geq x_0
|f(x)| \leq cg(x)$

\fi


\subsection*{Other asymptotic relations}
There are three other asymptotic notations in common use.  We include
them here for the record, but they will not be used further this term.

The tightest of the relationships between growth rates is
\emph{asymptotic equality}, $\sim$:
\begin{defin}
\[f \sim g \mbox{  iff  } \mbox{Lim}_{x\rightarrow \infty} {f(x) \over g(x)} = 1.\]
\end{defin}
This was the relation described in lecture for the Harmonic number
\[H_n \sim \ln n.\]

For example, $x + 1/x \sim x - \sqrt{x}$.  Note that if the values of $f$
and $g $ are nonegative, then $f \sim g \implies f = \Theta(g)$.

\emph{Exercise}:  Give an example of $f,g$ such that 
$f = \Theta(g)$ but \textbf{not} $f \sim g$.

To indicate that $g$ actually grows even faster than $f$, we can use
``Little Oh''notation:
\begin{defin}
$f = o(g) \mbox{  iff  } \forall c > 0 \exists x_0 \forall x \geq x_0: |f(x)|
\leq c g(x)$.
\end{defin}
This definition is a little hard to follow because of all the quantifiers.
For functions, $g$, which are nonnegative --- which is generally all we
care about in this context --- a clearer way to say $f=o(g)$ is:
\[\mbox{Lim}_{x\rightarrow \infty} {f(x) \over g(x)} = 0.\]

For example, the proof of Theorem~\ref{xlnx} above actually yielded a
the stronger result:

\begin{theorem}
\[{x\over {\ln x}} = o(x).\]
\end{theorem}

\begin{theorem}
\[\mbox{It is not true that }{x\over 100} = o(x).\]
\end{theorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of contradiction
that $x/100 = o(x)$.  Then for all $c > 0$, there exists an
$x_0$ such that for all $x \geq x_0$, $|x/100| \leq c x$.  In
particular, if $c = 1/200$, there must exist an $x_0$ such
that for all $x \geq x_0$, $|x/100| \leq x/200$.
Since this statement is false for all positive $x$, we have reached a
contradiction.
\end{proof}

Another, rarely used, asymptotic notation is ``Little Omega'',
$\omega()$, which is just the opposite of ``Little Oh'', $o()$.

\begin{defin}
$g = \omega(f) \mbox{  iff  } f = o(g)$
\end{defin}

For example, $x^2 = \omega(x)$ since $x^2$ grows strictly faster than
$x$.

\section{Can sum 'em}
\subsection{Perturbation Method}
We have seen some methods to find closed forms of sums.  Finding closed
form solutions is tricky business because it is not always the case that
they exist!  Let's carefully review the way to discover summation formulas
called the {\em perturbation} method in lecture.  As with all other
methods it only works sometimes.

\iffalse
Let $S_n = \sum_{i=0}^n a_i$. Then,
$$S_n + a_{n+1} = \sum_{i=0}^{n+1}a_i$$
$$S_n + a_{n+1} = a_0 + \sum_{i=1}^{n+1}a_i$$
$$S_n + a_{n+1} = a_0 + \sum_{i=0}^{n}a_{i+1}$$

How do we use this?
\fi

Consider the sum, $S_n = \sum_{i=0}^n ix^i$.

The general approach is to add the $(n+1)$st term to both sides,
\[
\begin{array}{lll}
S_n + (n+1)x^{n+1} &  = 0x^0 + \sum_{i=1}^{n+1}ix^i\\
& = \sum_{i=0}^{n}(i+1)x^{i+1}\\
& = \sum_{i=0}^{n}ix^{i+1} + \sum_{i=0}^{n}x^{i+1}\\
& = x\sum_{i=0}^n ix^i + x\sum_{i=0}^{n} x^{i}\\
& = xS_n + x(1-x^{n+1})/(1-x)
\end{array}
\]
Having found $S_n$ in the last expression, bring terms involving $S_n$ to
one side and solve,
\[(1-x)S_n = {{x(1-x^{n+1}) - (n+1)x^{n+1}(1-x)} \over (1-x)}\]
\[S_n= {{x-(n+1)x^{n+1}+nx^{n+2}} \over (1-x)^2}\]
 
\subsection{Integral Method}
Let us now go back to the integral method and see how to evaluate the sum
$$\sum_{i=1}^{\infty} \frac{1}{i^2}$$
In a similar fashion to the example in the lecture,
this sum, minus its first term, is less than the area under the curve
$y = 1/x^2$ from $1$ to $\infty$.  That it,
\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2} & = & 1 + \sum_{i=2}^{\infty} 
\frac{1}{i^2} \\
& \leq & 1 + \int_1^{\infty} x^{-2} dx \\
& = & 2.
\end{eqnarray*}
Thus, our infinite sum is at most $2$, and in particular it converges.
In fact, one can prove (using complex analysis) that the exact value
of the sum is $\pi^2 / 6$; we won't prove this here.

\subsection{Formal Manipulation}
Next let's look at the following {\em doubly infinite} sum
$$\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} x^i y^j,$$
where (critically) $$0 < x, y < 1.$$
We can therefore re-write this as
\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} x^i y^j & = &
\sum_{i=0}^{\infty} x^i \left( \sum_{j=0}^{\infty} y^j \right) \\
& = & \sum_{i=0}^{\infty} x^i \left( \frac{1}{1 - y} \right) \\
& = & \left( \frac{1}{1 - y} \right) \sum_{i=0}^{\infty} x^i \\
& = & \frac{1}{(1 - x) (1 - y)}.
\end{eqnarray*}

\section{Can't sum it!}

We note that the manipulations above were justified because we had a
series of positive real numbers whose sum converged.
Just to reinforce this, here's a case in which re-arrangements
of the sum are clearly not allowed.
Let 
$$S = \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots.$$
Consider the following:
$$S = [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0.$$
$$S = 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.$$
What's the problem here?  

If we define $S_n = \sum_{i=0}^{n}(-1)^i$ then $S_n = 1$ for odd $n$
and $S_n = 0$ for even $n$. Hence $S_n$ does not have a well-defined
limit as $n$ tends to infinity.  $S$ is not a convergent sum.

\section{Team Problems}

\begin{problems}

\problem We begin with two large glasses.  The first glass contains a pint
of water, and second contains a pint of wine.  We pour $1/3$ of a pint
from the first glass into the second, stir up the wine/water mixture in
the second glass, and then pour $1/3$ of a pint of the mix back into the
first glass.  We now repeat this pouring back-and-forth process a total of
$n$ times.
\bparts

\ppart
Describe a closed form formula for the amount of wine in the first glass
after $n$ back-and-forth pourings.

\ppart
What is the limit of the amount of wine in each glass as $n$ approaches infinity?
\eparts

\emph{Solution}: The state of the system of glasses/wine/water at the
beginning of a round of pouring and pouring back is determined by the
total amount of wine in the first glass.  Initially, the first glass
contains one pint of wine and no water.  Suppose the first glass contains
$w$ pints of wine, $0\leq w \leq 1$.  Since we're at the beginning of a
round, it contains one pint of liquid, and therefore contains $1-w$ pints
of water.  The second glass contains the rest of the wine and water.

Pouring 1/3 pint from first glass to second leaves 2/3 pint of liquid and
$(2/3)w$ wine in the first glass, and 4/3 pints liquid and $1 - (2/3)w$ wine
in the second glass.  Pouring 1/3 pint back from second into first
transfers a proportion of (1/3)/(4/3) of the wine in the second glass into
the first.  So the round completes with both glasses containing a pint of
liquid, and the first glass containing
\[(2/3)w + (1/4)(1- (2/3)w) = 1/4 + w/2\]
pints of wine.  After the second round, the first glass contains
\[1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/2^2\]
pints of wine, and after the $n$th round
\[
\begin{array}{lll}
w/2^n + \Sigma_{i=1}^n (1/2)^{i+1} &=  w/2^n + (1/2)\Sigma_{i=1}^n
(1/2)^{i}\\
& = w/2^n + (1/2)(-1 + \Sigma_{i=0}^n (1/2)^{i})\\
& = w/2^n + (1/2)(-1 + (1 - (1/2)^{n+1})/(1 - 1/2))\\
& = w/2^n - 1/2 + 1 - (1/2)^{n+1}\\
& = w/2^n + 1/2 - (1/2)^{n+1}.
\end{array}
\]
So when $w=0$ initially, the pints of wine in the first glass is
\[1/2 - (1/2)^{n+1}.\]
You would expect after a thorough mixing that the glasses would contain
the same amount of wine, viz. 1/2 pint.  Indeed, the limiting amount of
wine in the first glass approaches 1/2 from below as n approaches
infinity.  In fact, it approaches 1/2 no matter how the wine was initially
distributed.


\iffalse

\problem \textbf{(VARIANT OF F97.  COMMENTS PLEASE: SHOULD WE USE THIS?)}
Is a Harvard degree really worth more than an MIT degree?!  Let us say
that a person with a Harvard degree starts with \$40,000 and gets a
\$20,000 raise every year after graduation, whereas a person with an MIT
degree starts with \$30,000, but gets a 20\% raise every year.  Assume
inflation is a fixed $8\%$ every year.  That is, \$1.08 a year from now is
worth \$1.00 today.

\bparts

\ppart How much is a Harvard degree worth today if the holder will work
for $n$ years following graduation?

\ppart How much is an MIT degree worth in this case?

\ppart If you plan to retire after twenty years, which degree would
be worth more?

\eparts

\textbf{Solution to F97 problem}:

One dollar after year $i$ is worth $\frac{1}{(1+p)^i}$ in today's currency.

So $$H_n = \sum_{i=1}^{n} {10000i / (1+p)^i}$$
$$M_n = \sum_{i=1}^{n} {1000i^2 / (1+p)^i}$$
\begin{enumerate}
\item From lecture the sum 
$$\sum_{i=0}^{n} ix^i = 
{x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2}$$
So $$H_n = 10000({x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2})$$
for $x = 1/1.08$.

\item To calculate the sum $\sum_{i=0}^n i^2x^i$, let us
differentiate both sides of 
$$\sum_{i=0}^n ix^i = {x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2}$$
$$\sum_{i=0}^{n}i^2 x^{i-1} ={(1-x)^2(1-(n+1)^2x^n +n(n+2)x^{n+1}) +2(1-x)(x-(n+1)x^{n+1}+nx^{n+2}) \over (1-x)^4}$$
$$= {1 + x - (n+1)^2x^{n} + (2n^2+2n-1)x^{n+1} -n^2x^{n+2} \over (1-x)^3}$$
Multiplying both sides by $x$ we have:
$$\sum_{i=0}^{n}i^2 x^{i} = {x + x^2 - (n+1)^2x^{n+1} + (2n^2+2n-1)x^{n+2} -n^2x^{n+3} \over (1-x)^3}$$ 

So $$M_n = 1000({x + x^2 - (n+1)^2x^{n+1} + (2n^2+2n-1)x^{n+2} -n^2x^{n+3} \over (1-x)^3})$$


\item Take $x = 1/1.08$ and solve for $n$ such that $M_n \geq H_n$. We see that
$n = 17$ is a long enough wait for an MIT student to get ahead. After 
17 years, the MIT graduate has earned $M_{17} = \$674,680.28$ while the
Harvard graduate has earned only $H_{17} = \$657,099.62$.

\end{enumerate}
\fi


\problem
\bparts
\ppart Give an example of functions $f,g:\naturals\to\naturals$ such that
neither $f = O(g)$ nor $g = O(f)$.  Prove it.

\emph{Solution}: $f(n) = 1 + n(n \bmod 2), g(n) =1 + n ((1 + n) \bmod 2)$.
So $f(n)$ is $n$ times the size of $g(n)$ on odd $n$, vice-versa on even
$n$.

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

\emph{Solution}: False, let $f_i$ be a constant function with $f(n) =
b(i)$ for all $n$, where $b(i)$ is nonnegative and not $O(2^i)$, for
example, $b(i) = i2^i$.  So $f_i = O(1)$ for each $i$.  Now
\[\sum_{i=1}^n f_i(n) \geq f_n(n) = b(n) \neq O(2^n).\]
\eparts

\iffalse

\problem \textbf{(COMMENTS ON WHETHER YOU LIKE THIS.  Also, there are lots
of alternative choices of $\alpha$ and op which could be used.)}
Prove or give a counterexample: 
\[f = \alpha(g)\ \implies\  \mbox{op}(f) = \alpha(\mbox{op}(g)),\]

\bparts

\ppart when $\alpha()$ is $O()$ and $\mbox{ op}(x)=x^2$.
\ppart when $\alpha()$ is $O()$ and $\mbox{ op}(x)=2^x$.
\ppart when $\alpha()$ is $O()$ and $\mbox{ op}(x)=\log x$.
\ppart when $\alpha()$ is $o()$ and $\mbox{ op}(x)=\log x$.
\ppart when $\alpha()$ is $\sim$ and $\mbox{ op}(x)=x^2$.
\ppart when $\alpha()$ is $\sim$ and $\mbox{ op}(x)=2^x$.
\eparts
\fi


\end{problems}

\end{document}
