\documentstyle[11pt,twoside,amsfonts,amstex,psfig]{article}

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

\raggedbottom

\input{macros-course}

\begin{document}

\handout{recprobs5}{Problems for Recitation 5 (3/6/98)}{March 6, 1998}

\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

\problem
Asymptotic notations
\bparts

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

\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).\]
\eparts

\end{problems}

\end{document}






