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

\input{macros-course}

\newtheorem{falsethm}{False Theorem}

\begin{document}

\tutn{5}{3/5/99}{March 5, 1999}

\section{Some Sums}

\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!

\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$.  We saw in lecture that we
could obtain a closed from for this sum by taking derivatives of the
closed form for the geometric series $\sum_{i=0}^n x^i$.  The formula for
the geometric series was itself obtained by the {\em perturbation} method.

The {\em perturbation} method could also have been used directly on $S_n$.
For example,
\[
\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}\]
 
In general, the approach is to introduce a variable, $S_n$, for the sum,
form an expression involving $S_n$ --- commonly by adding the $(n+1)$st
term to $S_n$ --- simplify, and look for appearances of the sum itself in
some ``new'' way.  Then use the equation between the initial expression
and the simplified one to solve for $S_n$.

\subsection{Integral method}

Let us now go back to the integral method and see how to estimate 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 is,
\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*}

\subsection{And some you can't sum...}

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.

In general, problems arise when dealing with sums which are not
\emph{absolutely convergent}.  A series is absolutely convergent when the
sum of the \emph{absolute values} of the terms converge.  For example, the
series $1 - 1/2 + 1/3 - 1/4 \dots$ converges, but is not absolutely
convergent.

Here's an illustration of the kind of problem to watch out for: sometimes
we can simplify evaluation of a infinite series by rearanging the order of
its terms.  The value of an absolutely convergent series is unchanged by
rearranging the terms.  On the other hand, by rearranging the order of
terms in a series which is convergent but not absolutely convergent, the
rearranged series can be made to converge to \emph{any} desired value.
(It's fun to figure out how to do this with $1 - 1/2 + 1/3 - 1/4 \dots$.)

\section{Asymptotic Notations}

In many parts of mathematics and computer science, one needs to compare
growth rates of functions.  The most basic comparison notation in Computer
Science is ``Oh'' notation, $O()$.  Two other notations with simple
definitions in term of $O()$ are also convenient to have: $\Theta()$, and
$\Omega()$.

Intuitively, ``$f = O(g)$'' means that, to within a constant factor, $g$
grows ``at least as fast'' as $\abs{f}$.  More precisely, for functions
$f,g:\reals \to \reals$, we say that $f = O(g)$ iff $\abs{f}$ is bounded
above by some positive constant multiple of $g$ for any sufficiently large
argument of the functions.

Saying that a property holds for a ``sufficiently large'' number, means
that there is a real number $x_0$ such that the property holds for all
real numbers $\geq x_0$.  Here's the definition expressed as a logical
expression:

\begin{defin}
For functions $f,g:\reals \to \reals$,  define $f=O(g)$  to mean
\[\exists c>0\: \exists x_0\: \forall x \geq x_0\,:\ |f(x)| \leq c\cdot g(x).\]
\end{defin}

When we think of $f = O(g)$ as meaning roughly that $f \leq g$, the
property of transitivity is captured by

\begin{lemma}
If $f = O(g)$ and $g = O(h)$, then $f = O(h)$.
\end{lemma} 

\textbf{Class Exercise}: Prove the lemma.
\begin{proof}
$\abs{f(x)} \leq c\cdot g(x)$ for $x > x_0$ and $\abs{g(x)} \leq d\cdot
h(x)$ for $x > x_1$ implies  $\abs{f(x)} \leq (cd)\cdot
h(x)$ for all  $x > \max(x_0,x_1)$.
\end{proof}


The two other growth rate notations are defined in terms of $O()$.
Intuitively, $f = \Omega(g)$ corresponds to saying that $f \geq g$, and
$f= \Theta(g)$ corresponds to $f = g$, approximately.  Here are the
precise definitions:
\begin{defin}
\[f=\Omega(g) \mbox{    iff   } g = O(f),\]
and
\[f=\Theta(g) \mbox{   iff   } [f=O(g) \mbox{ and } g = O(f)].\]
\end{defin}


The value of these notations is that they highlight growth rates 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).\]
In words, we would say that ``$T(n)$ grows \emph{cubically},'' meaning it
is bounded both above and below by functions by constant multiples $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).\]

\iffalse
Here's a simple consequence of the definition:

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

\textbf{Class Exercise}: Prove Lemma~\ref{abO}.
\fi

\begin{lemma}\label{xlnx}
\[ {x \over {\ln x}} = O(x) \mbox{  but  } x \neq O({x \over {\ln x}}).\]
\end{lemma}

\begin{proof}
${x/ \ln x} < x$ as long as $x > 0$ and $\ln x > 1$, that is, when $x
> e$.  So $x / {\ln x} = O(x)$ by definition of $O()$ (with $x_0 = e$
and $c =1$).

To show the $\neq O()$ statement holds, we must show that for all $c > 0$
and all $x_0$, there is an $x_1 \geq x_0$, such that $\abs{x_1} > c
x_1/\ln x_1$.  But $\abs{x} > (c/\ln x) x = c (x/\ln x)$ if $c/ {\ln x} <
1$.  So let $x_1 = \max(e^c + \epsilon, x_0)$.
\end{proof}

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

\medskip

When we think of $f = O(g)$ as ordering $f$ below $g$, we have to think
about \emph{partial} orderings.  For example, neither of $\abs{x \sin x}$
nor $\abs{x \cos x}$ is $O()$ of the other -- because there are infinitely
many $x$'s where one is zero and the other is not, and no constant
multiple of zero can ``catch up'' with the positive value of the other.
This $O()$-incomparibility is not just confined to functions with an
infinite number of roots: consider $\abs{x \sin x} + \ln x$ and
$\abs{x \cos x} + \ln x$.

\subsection{Growth rates of common functions}

\begin{lemma}\label{mainO}
The main facts to remember are:

\begin{enumerate}

\item $p(x) = \Theta(x^n)$ for any polynomial $p$ of degree $n$ with
positive leading coefficient,

\item $x^a = O(x^b)$ and $x^b \neq O(x^a)$ for $0 \leq a < b$.

\item $x^k = O(a^x)$ and $a^x \neq O(x^k)$ for any $k>0, a>1$,

\item $a^x = O(b^x)$ and $b^x \neq O(a^x)$ for $1 \leq a < b$

\item $\ln(x)^k = O(x^\epsilon)$ and $ x^\epsilon \neq O(\ln(x)^k)$  for any $k,\epsilon >0$.

\end{enumerate}

\end{lemma}
These facts are most easily proved using elementary calculus.  For the
record, we include some of the proofs in an Appendix.  These proofs will
not be presented in tutorial and will not be required material.

Some additional useful rules (with elementary proofs directly from the
definitions) are

\begin{enumerate}

\item $f \pm g = O(\max(\abs{f}, \abs{g}))$,

\item $f \cdot  g = O(\abs{f} \cdot \abs{g}))$.

\item If $f(x) = O(g(x))$ and $\lim_{x \rightarrow \infty} h(x) = \infty$, then
     $f(h(x)) = O(g(h(x))$.

\end{enumerate}

Other operations may not behave so nicely, e.g.,

\textbf{Class exercise}: Show that $2x = O(x)$ but $2^{2x} \neq O(2^x)$.
\begin{proof}
$2^{2x} = (2^x)^2 = y^2$ where $y = 2^x$.  But we know $y^2 \neq O(y)$, and since $y
\rightarrow \infty$ as $x \rightarrow \infty$, so $2^{2x} = (2^x)^2 \neq O(2^x)$.
\end{proof}


\subsection{A note on O notation}

Sometimes you may see an 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$.

\subsection{Other asymptotic relations}

There are three other asymptotic notations in common use.  We include
them here for the record, but will not use them much this term. 

The tightest of the relationships between growth rates is
\emph{asymptotic equality}, $\sim$:
\begin{defin}
\[f \sim g \mbox{  iff  } \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 nonnegative, then $f \sim g$ implies  $f = \Theta(g)$.

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

To indicate that $g$ actually grows at a faster rate 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 :
\abs{f(x)} \leq c g(x)$.
\end{defin}
This definition is a little hard to follow because of all the quantifiers.
For functions, $f, g$, which are nonnegative --- which is generally all we
care about in this context --- a clearer way to say $f=o(g)$ is:
\[\lim_{x\rightarrow \infty} {f(x) \over g(x)} = 0.\]

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

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

Note that

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

\begin{proof}
$\lim_{x \rightarrow \infty} (x/100)/x = 1/100 \neq 0$.
\end{proof}

For comparison purposes, it helps to express $O()$ as a similar statement
about limits.  If $f$ and $g$ are nonnegative functions, then $f = O(g)$ iff
there a constant $c \geq 0$ such that
\[
 \limsup_{x\rightarrow \infty} {f(x) \over g(x)} \leq c.
\]

Now it's easy to see that $f= o(g)$ implies $f = O(g)$ and $g \neq O(f)$.
The converse implication may fail in general, but it's important to note
that

\begin{lemma}
Each of the statements of the form ``$f = O(g)$ and $g \neq O(f)$'' in
Lemma~\ref{mainO}, could have been replaced by ``$f= o(g)$''.
\end{lemma}

For example, $x^a = o(x^b)$ where $0 \leq a < b$.

\medskip

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$.

\subsection{Induction and asymptotic notation}

One has to be careful when combining inductive proofs with asymptotic
notation.  Here is an 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.

\section{Team Problems}

\begin{problems}

\problem 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?

\textbf{Solution}:
One dollar after year $i$ is worth $r^i$ in today's currency, where
\[
r={1 \over 1+p} = {1 \over 1.08} = 0.925\, 925\, 925 \dots
\]
So 
\begin{eqnarray*}
\mbox{Hvd}_n & = & \sum_{i=0}^{n} (40000+ 20000i)r^i\\
        & = & 40000\sum_{i=0}^{n} r^i + 20000\sum_{i=0}^{n} i r^i,\\
\mbox{MIT}_n & = & 30000\sum_{i=0}^{n} {1.2}^i r^i\\
        & = & 30000\sum_{i=0}^{n} (1.2r)^i
\end{eqnarray*}

We saw above that 
\[
\sum_{i=0}^{n} ir^i = {{r - (n+1) r^{n+1} + n r^{n+2}} \over (1-r)^2},
\]
so 
\begin{eqnarray*}
\mbox{Hvd}_n & = & 40000{(1- r^{n+1}) \over 1- r}  + 
                   20000{(r - (n+1) r^{n+1} + n r^{n+2}) \over (1-r)^2}\\
  & = & {20000(2(1- r^{n+1} -r +r^{n+2}) + r - (n+1) r^{n+1} + n r^{n+2}) \over (1-r)^2}\\
  & = & {{20000(2 - 2r - (n-1)r^{n+1} + (n + 2)r^{n+2})} \over (1-r)^2}\\
  & = & {{20000(2 - 2r - 19r^{21} + 22r^{22})} \over (1-r)^2} = 1,532,285,\\
\mbox{MIT}_n & = & {{30000(1 - (1.2r)^{21})} \over 1 - r} = 3,296,368,
\end{eqnarray*}

so the MIT degree is more than twice as valuable!
\eparts

\problem We begin with two large glasses.  The first glass contains a pint
of water, and the second contains a pint of wine.  We pour some fixed
fraction, $f$, of a pint from the first glass into the second, stir up the
wine/water mixture in the second glass, and then pour the same fraction
$f$ 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?


\emph{Solution with $f = 1/3$}: 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 water and no wine.  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.
\eparts

\iffalse
\problem
\bparts
\ppart Let $f(n) =  n\cdot [n \bmod 2]$,  and  $g(n) = n \cdot [(n + 1) \bmod 2]$.
Show that neither $f = O(g)$ nor $g = O(f)$.

\ppart Generalize the previous part to show an infinite sequence of
functions $f_1, f_2, f_3, \dots$ such that neither $f_i = O(f_j)$ nor $f_j
= O(f_i)$ for all $i \neq j$.
\eparts

\problem
\bparts
\ppart Prove that if $\lim_{x\rightarrow \infty} g(x) = \infty$ and $f = O(g)$, then
$\ln f = O(\ln g)$.

\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}

\ppart Show that the condition $\lim_{x\rightarrow \infty} g(x) =
\infty$ in the previous part is necessary.
\eparts
\fi

\end{problems}

\appendix

\section{Appendix: proofs about $O()$}

\begin{theorem}\label{lno}
\[\forall \epsilon > 0: \ln x = O(x^\epsilon).\]
\end{theorem}

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

\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}


\end{document}

