\documentclass[11pt,twoside]{article}

\usepackage{macros-course-lectures}
\usepackage{graphics}
\usepackage[pdflatex]{graphicx}

\newenvironment{verify}{\par{\noindent\em Verification.}\hspace{1em}\setlength{\parindent}{3ex}}{\qed}

\newtheorem{guess}[theorem]{Guess}
\newtheorem*{guess*}{Guess}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{method}{Method}

\mainlylecture
\breakper

\begin{document}

\lecture{notes11}{Summations and Recurrences}{15 March 2001}

\forlecture{{\bf remember to introduce $\sim$ notation.}}

This lecture covers several topics.  While we can prove that a
summation formula is correct by induction, finding such formulas in
the first place is still difficult.  In the first section, we will
give a general approach to this problem.  The second topic is
evaluation of products.  In particular, we'll obtain bounds on the
familiar product $n!$.  The third topic is asymptotic notation; this
is a cryptic shorthand that conveys information about the behavior of
a function $f(n)$ for large $n$. 

Having developed tools for sums and products, we will begin studying
ways to solve \emph{recurrences}.  Needless to say, recurrences come
up again and again.  In particular, recurrences often arise in the
analysis of recursive algorithms.

\section{Finding Summation Formulas}

The source of the simple formula $\sum_{i=1}^n i = \frac{n(n+1)}{2}$
is still a mystery!  Sure, we can prove this statement true by
induction, but where did the expression on the right come from?  Even
more inexplicable is the summation formula for consecutive squares:

\begin{eqnarray*}
\sum_{i=1}^n i^2 & = & \frac{(2n+1)(n+1)n}{6} \\
                 & = & \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} \\
                 & \sim & \frac{n^3}{3}
\end{eqnarray*}

Here is how we might find the sum-of-squares formula if we forgot it
or had never seen it.  First, the Integral Method gives a quick
estimate of the sum:

\begin{eqnarray*}
\int_0^n x^2 \ dx \leq \sum_{i=1}^n i^2 \leq \int_0^n (x+1)^2 \ dx \\
\frac{n^3}{3} \leq \sum_{i=1}^n i^2 \leq \frac{(n+1)^3}{3} - \frac{1}{3}
\end{eqnarray*}

These upper and lower bounds obtained by the Integral Method show that
$\sum_{i=1}^n i^2 \sim \frac{n^3}{3}$.  To get an exact formula, we
then guess the general form of the solution.  Where we are uncertain,
we can add parameters $a, b, c, \ldots$.  For example, we might make
the guess:

\[
\sum_{i=1}^n i^2 = an^3 + bn^2 + cn + d
\]

If the guess is correct, then we can determine the parameters $a$,
$b$, $c$, and $d$ by plugging in a few values for $n$.  Each such
value gives a linear equation in $a$, $b$, $c$, and $d$.  If we plug
in enough values, we may get a linear system with a unique solution.
Applying this method to our example gives:

\begin{eqnarray*}
n = 0 & \rightarrow & 0 = d \\
n = 1 & \rightarrow & 1 = a + b + c + d \\
n = 2 & \rightarrow & 5 = 8a + 4b + 2c + d \\
n = 3 & \rightarrow & 14 = 27a + 9b + 3c + d
\end{eqnarray*}

Solving this system gives the solution $a = 1/3, b = 1/2, c = 1/6, d =
0$.  Therefore, if our initial guess at the form of the solution was
correct, then the summation is equal to $n^3/3 + n^2/2 + n/6$.  In
fact, our initial guess {\em was} correct, this is the right formula
for the sum of squares!

{\em Be careful!}  After obtaining a formula by this method, always go
back and prove it using induction or some other method.  This is not
merely a check for algebra blunders; if the initial guess at the
solution was not of the right form, then the resulting formula will be
completely wrong!

\section{Double Sums}

Sometime we have to evaluate sums of sums, otherwise known as
\emph{double summations}.  Sometimes it is easy: we can evaluate the
inner sum, replace it with a closed form, and then evaluate the outer
sum which no longer has a summation inside it.

But there's a special trick that is often extremely useful for sums,
which is \emph{exchanging the order of summation.}  It's best
demonstrated by example.  Suppose we want to compute the sum of the
harmonic numbers
\[
\sum_{k=1}^n H_k = \sum_{k=1}^n \sum_{j=1}^k 1/j
\]
For intuition about this sum, we can try the integral method:
\[
\sum_{k=1}^n H_k \approx \int_{k=1}^n \ln n \approx n\ln n-n.
\]

Now let's look for an exact answer.  If we think about the pairs
$(k,j)$ over which we are summing, they form a triangle:
\[
\begin{array}{c|ccccccc}
 &j&1&2&3&4&\cdots&n\\
\hline
k\\
1&1\\
2 &1&1/2\\
3 &1&1/2&1/3\\
4 &1&1/2&1/3&1/4\\
 &\cdots\\
n &1&1/2&&\cdots&&&1/n
\end{array}
\]
The summation above is summing each row and then adding the row sums.
Instead, we can sum the columns and then add the column sums.
Inspecting the table we see that this double sum can be written as
\begin{align*}
\sum_{k=1}^n H_k &= \sum_{k=1}^n \sum_{j=1}^k 1/j\\
&= \sum_{j=1}^n \sum_{k=j}^n 1/j\\
&= \sum_{j=1}^n 1/j \sum_{k=j}^n 1\\
&= \sum_{j=1}^n \frac1j (n-j+1)\\
&= \sum_{j=1}^n \frac{n-j+1}j \\
&= \sum_{j=1}^n \frac{n+1}j - \sum_{j=1}^n \frac{j}{j}\\
&= (n+1)\sum_{j=1}^n \frac1j - \sum_{j=1}^n 1\\
&= (n+1)H_n-n
\end{align*}

\section{Computing Products:  Estimating \protect{$n!$}}

Sometimes one encounters product notation instead of summation
notation.  By far the most common product is factorial:

\[
n! = 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n = \prod_{i=1}^n i
\]

Our goal in this section is to find a good, closed-form estimate of
$n!$.  The best way to handle a product is to convert it into a sum by
taking the logarithm.  In the case of factorial, this gives:

\begin{eqnarray*}
\ln n! & = & \ln(1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n) \\
       & = & \ln 1 + \ln 2 + \ln 3 + \ldots + \ln(n-1) + \ln n \\
       & = & \sum_{i=1}^n \ln i
\end{eqnarray*}

We've not seen a summation containing a logarithm before!
Fortunately, one tool that we used in evaluating sums is still
applicable: the Integral Method.  We can bound the terms of this sum
with $\ln x$ and $\ln(x+1)$ as shown in Figure~\ref{fig:integral2}.
This gives bounds on $\ln n!$ as follows:

\begin{eqnarray*}
\int_1^n \ln x \ dx \leq & \sum_{i=1}^n \ln i & \leq \int_0^n \ln(x+1) \ dx \\
n \ln(\frac{n}{e}) + 1 \leq & \sum_{i=1}^n \ln i & \leq (n+1) \ln\left(\frac{n+1}{e}\right) + 1 \\
\left(\frac{n}{e}\right)^n e \leq & n! & \leq  \left(\frac{n+1}{e}\right)^{n+1} e
\end{eqnarray*}


\begin{Figure}[htbp]
\centerline{%
%\psfig{figure=figures/integral2.eps,height=2in}
\includegraphics[height=2in]{figures/integral2}
}
\caption{\em This figure illustrates the Integral Method for bounding
the sum $\sum_{i=1}^n ln \ i$.}
\label{fig:integral2}
\end{Figure}

The second line follows from the first by completing the integrations.
The third line is obtained by exponentiating.

We now have a closed form estimate of $n!$; namely, $n!
\approx (\frac{n}{e})^n$.  (We are ignoring stray $e$ and $n$
factors.)  A more accurate estimate of $n!$ can be obtained with a
more careful calculation:

\begin{fact}[Stirling's Formula]
\[
\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{1/(12n+1)}
\leq n! \leq
\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n  e^{1/12n}
\]
\end{fact}

The fact implies that $n! \sim (\frac{n}{e})^n \sqrt{2 \pi n}$, since
$e^{1/(12n+1)}$ and $e^{1/12n}$ both approach 1 as $n$ grows large.
These inequalities can be verified by induction, but the details are
nasty.  In fact, Stirling's formula is actually given incorrectly in
the popular algorithms book used in 6.046.

Though there is no closed form for $n!$, the bounds in Stirling's
formula are very tight.  For example, if $n = 100$, then Stirling's
bounds are:

\begin{eqnarray*}
100! & \geq & \sqrt{200 \pi} \left(\frac{100}{e}\right)^{100} e^{1/1201} \\
100! & \leq & \sqrt{200 \pi} \left(\frac{100}{e}\right)^{100} e^{1/1200}
\end{eqnarray*}

The only difference between the upper bound and the lower bound is in
the final term.  In particular $e^{1/1201} \approx 1.00083299$ and
$e^{1/1200} \approx 1.00083368$.  As result, the upper bound is no
more than $1 + 10^{-6}$ times the lower bound.  This is amazingly
tight!  Remember Stirling's formula; we will use it often.

\subsection{Double Summing}

Another way to derive Stirling's approximation is to remember that
$\ln n$ is roughly the same as $H_{n}$.  This lets us use the result
we derived before for $\sum H_k$ via double summation.  Our
approximation for $H_k$ told us that $\ln(k+1)\le H_k \le 1+\ln k$.
Rewriting, we find that $H_{k}-1 \le \ln k \le H_{k - 1}$.  It follows
that (leaving out the $i=1$ term in the sum, which contributes 0),
\begin{eqnarray*}
\sum_{i=2}^n \ln i &\le & \sum_{i=2}^n H_{i-1}\\
&= &\sum_{i=1}^{n-1} H_i\\
&= &nH_{n-1}-n\\
&\le &n(1+\ln(n-1))-n\\
&=&n\ln(n-1),
\end{eqnarray*}
roughly the same bound as we proved before via the integral method.
We can derive a similar lower bound.



\section{Asymptotic Notation}

Asymptotic notation is a shorthand used to give a quick measure of the
behavior of a function $f(n)$ as $n$ grows large.

The $\sim$ notation used previously is an example of asymptotic
notation.  Recall that $f(n) \sim g(n)$ means $\lim_{n \rightarrow
  \infty} \frac{f(n)}{g(n)} \rightarrow 1$.  For example, we used this
notation to describe the growth of the Harmonic numbers:

\begin{eqnarray*}
H_n & = &\sum_{i=1}^n \frac{1}{i} \\
    & = & \ln n + \gamma + \frac{1}{2n} + \frac{1}{12n^2} +
          \frac{\epsilon(n)}{120n^4} \\
    & \sim & \ln n
\end{eqnarray*}

In other words, $\lim_{n \rightarrow \infty} \frac{H_n}{\ln n} = 1$,
since the remaining terms become irrelevant as $n$ grows large.

There are other forms of asymptotic notation besides $\sim$, however.
In particular, there are 5 other symbols to learn:

\begin{itemize}
\item $O$ -- ``Oh'' or ``Big Oh''
\item $o$ -- ``Little Oh''
\item $\Theta$ -- ``Theta''
\item $\omega$ -- ``Little Omega''
\item $\Omega$ -- ``Omega''
\end{itemize}

Learning notation can be a bit irritating, but these symbols will be
used heavily in 6.046, 6.045, and other courses.  

\subsection{Big Oh}

Big Oh is the most frequently used asymptotic notation.  It is used to
give an upper bound on the growth of a function, such as the running
time of an algorithm.

\begin{defin*}
Given functions $f, g : {\cal R} \mapsto {\cal R}$, we say that $f(x)
= O(g(x))$ if there exists a constant $c > 0$ and an $x_0$ such that
for all $x \geq x_0$, $|f(x)| \leq c g(x)$.
\end{defin*}

This definition is rather complicated, but the idea is simple; the
statement $f(x) = O(g(x))$ means that $f$ grows no faster than $g$.
More precisely, $f$ is smaller than some constant times $g$ for all
sufficiently large values of $x$.  In a sense, $f(x) = O(g(x))$means
$f(x) \leq g(x)$, except that we're willing to ignore a constant
factor ($c$) and to allow exceptions for small $x$ (\ie, $x <
x_0$).


These are many ways of expressing the idea $f(x) = O(g(x))$.
Sometimes people will write $f(x) \leq O(g(x))$, $f(x)$ is $O(g(x))$,
$f(x) \in O(g(x))$, or $f(x)$ ``is on the order of'' $g(x)$.  These
all mean the same thing.

We are ready for some examples.  First, is $x = O(x^2)$?  It seems
that the answer should be ``yes'', because $x$ grows no faster than
$x^2$.  The following theorem proves this intuition correct.

\begin{theorem}
If $f(x) = x$ and $g(x) = x^2$, then $f(x) = O(g(x))$.
\end{theorem}

\begin{proof}
We must prove that there exists a constant $c > 0$ and an $x_0$ such
that for all $x \geq x_0$, $|x| \leq c x^2$.  In particular, we can
choose $c = 1$ and $x_0 = 1$.  Then for all $x \geq 1$, $|x| \leq 1
\cdot x^2$.
\end{proof}

As a shorthand, the statement of the preceding theorem could have been
written $x = O(x^2)$.  In fact, this notation is widely used, but we
will see that it introduces ambiguities that can be very difficult to
sort out.

How about the reverse statement, $x^2 = O(x)$?  This is not true;
$x^2$ grows faster than $x$ asymptotically.

\begin{theorem}
$x^2 \neq O(x)$
\end{theorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that $x^2 = O(x)$.  Then there exists a constant $c > 0$
and an $x_0$ such that for all $x \geq x_0$, $|x^2| \leq c x$.  This
implies that for all $x \geq x_0$, $x \leq c$.  However, this is false
for $x \geq \max(c + 1, x_0)$.
\end{proof}

The statement $x^2 = O(x)$ is false because $x$ grows too slowly.  We
might hope, therefore, that $x^2 = O(100x)$ is true because $100x$
grows much more quickly that $x$.  This statement is also false,
however.  The proof is the same as before.  The factor of 100 does not
matter; eventually, the quadratic function $x^2$ will grow much faster
and get much bigger than the linear function $100x$.

\begin{theorem}
$100x^2 = O(x^2)$
\end{theorem}

\begin{proof}
Choose $c = 100$ and $x_0 = 1$.  Then the theorem holds, since for all
$x \geq 1$, $|100x^2| \leq 100 x^2$
\end{proof}

\begin{theorem}
$x^2 + 100x + 10 = O(x^2)$
\end{theorem}

\begin{proof}
Choose $c = 111$ and $x_0 = 1$.  Then the theorem holds, since for all
$x \geq 1$, $|x^2 + 100x + 10| \leq 111 x^2$.
\end{proof}

We can generalize the preceding theorem to an arbitrary quadratic
polynomial.

\begin{theorem}
$a_1 x^2 + a_2 x + a_3 = O(x^2)$
\end{theorem}

\begin{proof}
Choose $c = |a_1| + |a_2| + |a_3|$ and $x_0 = 1$.  Then the theorem
holds, since for all $x \geq 1$, $|a_1 x^2 + a_2 x + a_3| \leq (|a_1|
+ |a_2| + |a_3|) x^2$.
\end{proof}

Intuitively, exponential functions grow faster than polynomials, even
very high degree polynomials.

\begin{theorem}
$x^{10} = O(e^x)$
\end{theorem}

\begin{proof}
Choose $c = 1$ and $x_0 = e^5$.  It can be proven using calculus that
$10 \ln x \leq x$ for all $x \geq e^5$.  Exponentiating gives that for
all $x \geq e^5$, we have $e^{10 \ln x} \leq e^x$ or equivalently
$x^{10} \leq e^x$.
\end{proof}

Big Oh notation is especially useful when describing the running time
of an algorithm.  For example, suppose that an algorithm for
multiplying $n \times n$ matrices runs in cubic time.  This fact can
be expressed concisely by saying that the running time is $T(n) =
O(n^3)$.  This allows the speed of an algorithm to be discussed
without reference to constant factors or lower-order terms that might
be machine specific.

Just knowing that the running time of an algorithm is $O(n^3)$ is
useful, because if $n$ doubles we can predict that the running time
will increase by a factor of about $8$ for large $n$.  In this way,
Big Oh notation preserves information about the scalability of an
algorithm or system.  Scalability is, of course, a big issue in the
design of algorithms and systems.

\subsection{Variants on Big Oh}

There are several other notations that closely parallel the Big Oh.

\begin{definition}
We say $f(x) = \Omega(g(x))$ if and only if $g(x)=O(f(x))$.  We say
$f(x)=\Theta(g(x))$ if and only if $f(x)=O(g(x))$ and $g(x)=O(f(x))$.
\end{definition}

More intuitively, $f(x) = \Omega(g(x))$ means ``$f(x)$ is eventually
bigger than $g(x)$'' while $f(x)=\Theta(g(x))$ means ``$f(x)$ is
roughly the same as $g(x)$.''

\begin{definition}
We say $f(x) = o(g(x))$ if $\lim_{x \rightarrow \infty} f(x)/g(x)=0$.
Equivalently, we say $g(x)=\omega(f(x))$.
\end{definition}

More intuitively, $f(x)=o(g(x))$ means $f$ is infinitesimally small
compared to $g$.  In contrast, $f(x)=O(g(x))$ means $f$ is smaller,
but not necessarily infinitesimal. 

\subsection{Pitfalls with Big Oh}

\forstudents[Study the things that can go wrong with Big Oh]{

There is a long list of ways to make mistakes with Big Oh notation.
This section presents some of the ways that Big Oh notation can lead
to ruin and despair.

\subsubsection*{The Exponential Fiasco}

Sometimes relationships involving Big Oh are not so obvious.  For
example, one might guess that $4^x = O(2^x)$ since 4 is only a
constant factor larger than 2.  This is reasoning is incorrect,
however; actually $4^x$ grows much faster than $2^x$.

\begin{theorem}
$4^x \neq O(2^x)$
\end{theorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that $4^x = O(2^x)$.  Then there exists a constant $c >
0$ and an $x_0$ such that for all $x \geq x_0$, $|4^x| \leq c2^x$.  This
implies that for all $x \geq x_0$, $2^x \leq c$.  But this assertion
is false for $x \geq \max(\ln(c + 1), x_0)$.
\end{proof}

\subsubsection*{Constant Confusion}

Every constant is $O(1)$.  For example, $17 = O(1)$.  This is true
because if we let $f(x) = 17$ and $g(x) = 1$, then there exists a $c >
0$ and an $x_0$ such that $|f(x)| \leq c g(x)$.  In particular, we
could choose $c$ = 17 and $x_0 = 1$, since $|17| \leq 17 \cdot 1$ for
all $x \geq 1$.  Since we can prove that any constant is $O(1)$, we
can show that for all $n$, $n = O(1)$.

Now here is the key question: Is $n = O(1)$?  Didn't we just answer
this?  Not quite.  This question is ambiguous; there are two possible
interpretations of the notation, and these give rise to two different
answers!

The core problem is that $n$ can refer to either of two functions.  On
the one hand, $n$ might refer to the constant function that takes on
the value $n$ everywhere.  That is, by $n$ we mean the function $f$
where for all $x$, $f(x) = n$.  In this case, $n = O(1)$ as we showed
above.

On the other hand, $n$ might refer to the function that grows
linearly.  In this case, by $n$ we mean the function $f$ where for all
$n$, $f(n) = n$.  Now $n \neq O(1)$.

The reason that this confusion is particularly associated with $O(1)$
and not with $O(\ln n)$ or $O(x^2)$ is that $O(1)$ contains no
reference to a variable.

If we ask, ``Is $n = O(\ln n)$?'', then it is fairly clear that $n$
refers to the function that grows linearly, and the answer is no.  On
the other hand if we ask, ``Is $n = O(\ln x)$?'', then probably $n$
refers to the constant function that takes on value $n$ everywhere,
and the answer is yes.  However, if we ask, ``Is $n = O(1)$?'', then
we do not know what function $n$ represents, and we can not say for
certain.

We can construct a false theorem that exploits this ambiguity.

\begin{falsethm}
\[
\sum_{i=1}^n i = O(n)
\]
\end{falsethm}

Recall that in reality $\sum_{i=1}^n i = n(n+1)/2 \neq O(n)$.

\begin{proof}
Define $f(n) = \sum_{i=1}^n i = 1 + 2 + 3 + \ldots + n$.  Since we
have shown that every constant $i$ is $O(1)$, $f(n) = O(1) + O(1) +
\ldots + O(1) = O(n)$.
\end{proof}

The error stems from confusion over what is meant in the statement $i
= O(1)$.  It is true that $i = 1, 2, 3$, and even the first 100 values
of $i$ are $O(1)$.  But not all values are $O(1)$; for example, the
last value of $i$ in the summation is equal to $n$ is therefore not
$O(1)$.  To avoid this error, just do not use $i = O(1)$ if there is
any chance $i$ can grow with a parameter.

\subsubsection*{Induction Destruction}

Let's try to prove the same false theorem another way.

\begin{falsethm}
\[
\sum_{i=1}^n i = O(n)
\]
\end{falsethm}

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the predicate that
$f(n) = O(n)$ where $f(n) = \sum_{i=1}^n i$.  In the base case, $P(1)$
is true because $f(1) = 1 = O(1)$.  In the inductive step, assume that
$f(n) = O(n)$ to prove that $f(n+1)$ is $O(n)$.  Observe that $f(n +
1) = f(n) + (n+1) = O(n) + O(n) = O(n)$.
\end{proof}

There is no error in the proof; the problem is that the proof does not
imply the theorem!  We have proven that for all $n \geq 1$,
$\sum_{i=1}^n i = O(n)$.  More precisely, this says that for each $n
\geq 1$, the constant represented by the summation $\sum_{i=1}^n i$
is $O(n)$.  This is true; in fact, every constant is $O(1)$.  What we
wanted to prove was that the function $f(n) = \sum_{i=1}^n i$ is
$O(n)$.  The notation obscures this essential distinction.

In general, never mix induction and Big Oh notation.  Instead, here is
a correct approach to proving an asymptotic upper bound by induction.
Let $f(n) = \sum_{i=1}^n i$.  To prove that $f(n) = O(n)$, we have to
show that there exists a constant $c > 0$ and an $n_0$ such that for
all $n \geq n_0$, $f(n) \leq cn$.  Suppose we choose and try to prove
the false theorem by induction on $n$.

{\em Proof (attempt). } The proof is by induction.  Let $P(n)$ be the
predicate that $f(n) \leq cn$.  In the base case, $P(1)$ is true
because $f(1) \leq c$.  {\em (Let's assume that we chose $c$ large
enough so that this holds.)} In the inductive step, assume that $f(n)
< cn$ to prove that $f(n+1) \leq c(n+1)$.  By the definition of
$f(n)$, we have $f(n+1) = f(n) + n + 1$.  By induction, this is at
most $cn + n + 1 = (c+1)n + 1$.

Now we are stuck; to complete the inductive step, we must prove that
$(c+1)n + 1 \leq c(n+1)$.  However, this is simply not true,
regardless of how large a value $c$ is chosen.  If $n$ becomes very
large, then the left side of the inequality is about $(c +1)n$, and
the right side is about $cn$.  Therefore, the inequality does not hold
and the proof does not go through.

\subsubsection*{Lower Bound Blunder}

Sometimes people incorrectly use Big Oh in the context of a lower
bound.  For example, they might say, ``The running time is at least
$O(n^2)$.''  We have defined a meaning for $f(n) = O(g(n))$ and
assigned the same meaning to $f(n) \leq O(g(n))$, but $f(n) \geq
O(g(n))$ is meaningless.  In the next section we will introduce
asymptotic notation to describe lower bounds.
}

\section{The Towers of Hanoi}

In the Towers of Hanoi problem, there are three posts and seven disks
of different sizes.  Each disk has a hole through the center so that
it fits on a post.  At the start, all seven disks are on one post as
shown in Figure~\ref{fig:hanoi}.  The disks are arranged by size so
that the smallest is on top and the largest is on the bottom.  The
goal is to end up with all seven disks in the same order, but on a
different post.  This is not trivial because of two restrictions.
First, the only permitted action is removing the top disk from a post
and dropping it onto another post.  Second, a larger disk can never
lie above a smaller disk on any post.  (These rules imply, for
example, that it is not fair to pick up the whole stack of disks at
once and then to drop them all on another post!)


\begin{Figure}[htbp]
\centerline{\includegraphics[height=1.5in]{figures/hanoi}}
\caption{\em This is the starting position in the Towers of Hanoi
problem.  All seven disks are stacked on the leftmost post.  The goal
is to move all the disks to a different post.  At each step the top
disk on a post can be removed and dropped onto another post.  At no
time, however, can a larger disk lie above a smaller disk.}
\label{fig:hanoi}
\end{Figure}

It is not immediately clear that a solution to this problem exists;
maybe the rules are so stringent that the disks cannot all be moved
to another post!

% We will represent the state of the Towers of Hanoi using diagrams like
% the one below.  The picture on the left is the initial state of the
% Towers as shown in Figure~\ref{fig:hanoi}.  In the picture on the
% right, all of the disks are on the middle post.  This is one of the
% two possible final states.  (In the other permissible final state, all
% disks are on the rightmost post.)
%
% \[
% \begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
% & 1 & & \\
% & 2 & & \\
% & 3 & & \\
% & 4 & & \\
% & 5 & & \\
% & 6 & & \\
% & 7 & & \\ \hline \hline
% \end{array}
% \Rightarrow
% \begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
% & & 1 & \\
% & & 2 & \\
% & & 3 & \\
% & & 4 & \\
% & & 5 & \\
% & & 6 & \\
% & & 7 & \\ \hline \hline
% \end{array}
% \]

One approach to this problem is to consider a simpler variant with
only three disks.  We can quickly exhaust the possibilities of this
simpler puzzle and find a 7-move solution like the one shown below.
(The disks on each post are indicated by the numbers immediately to
the right.  Larger numbers correspond to larger disks.)

\begin{nobreakperiods}
\begin{eqnarray*}
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
& 1 & & \\
& 2 & & \\
& 3 & & \\ \hline \hline
\end{array}
& \Rightarrow & 
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
&   &   & \\
& 2 &   & \\
& 3 & 1 & \\ \hline \hline
\end{array}
\Rightarrow
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
&   &   &   \\
&   &   &   \\
& 3 & 1 & 2 \\ \hline \hline
\end{array} \\
& \Rightarrow &
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
&   &   &   \\
&   &   & 1 \\
& 3 &   & 2 \\ \hline \hline
\end{array}
\Rightarrow
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
&   &   &   \\
&   &   & 1 \\
&   & 3 & 2 \\ \hline \hline
\end{array} \\
& \Rightarrow &
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
&   &   &   \\
&   &   &   \\
& 1 & 3 & 2 \\ \hline \hline
\end{array}
\Rightarrow
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
&   &   &   \\
&   & 2 &   \\
& 1 & 3 &   \\ \hline \hline
\end{array} \\
& \Rightarrow &
\begin{array}{p{0.4cm}|p{0.75cm}|p{0.75cm}|p{0.4cm}}
&   & 1 &   \\
&   & 2 &   \\
&   & 3 &   \\ \hline \hline
\end{array}
\end{eqnarray*}
\end{nobreakperiods}

This problem was invented in 1883 by the French mathematician Edouard
Lucas.  In his original account, there were 64 disks of solid gold.
At the beginning of time, all 64 were placed on a single post, and
monks were assigned the task of moving them to another post according
to the rules described above.  According to legend, when the monks
complete their task, the Tower will crumble and the world will end!

The questions we must answer are, ``Given sufficient time, can the
monks succeed?'' and if so, ``How long until the world ends?'' and,
most importantly, ``Will this happen before the 6.042 final?''

\subsection{Finding a Recurrence}

The Towers of Hanoi problem can be solved in a recurrent fashion as
follows.  Let $T_n$ be the minimum number of steps needed to move an
$n$-disk tower.  For example, it is not hard to see that $T_1 = 1$ and
$T_2 = 3$.  For 3 disks, the solution given above shows that $T_3 \leq
7$.  We can generalize the approach used for 3 disks to the following
recursive algorithm for $n$ disks.

{\bf Step 1.  } Move the top $n-1$ disks from the first post to the
third post.  This can be done recursively in $T_{n-1}$ steps.

{\bf Step 2.  }  Move the largest disk from the first post to the to
the second post.  This requires just 1 step.

{\bf Step 3.  } Move the $n-1$ disks from the third post onto the
second post.  Again, $T_{n-1}$ steps are required.

This algorithm shows that $T_n$, the number of steps required for $n$
disks, is at most $T_n \leq 2 T_{n-1} + 1$.  We can now compute upper
bounds on the number of steps required for various numbers of disks.

\begin{eqnarray*}
T_3 & \leq & 2 \cdot T_2 + 1 \\
    & = & 7 \\
T_4 & \leq & 2 \cdot T_3 + 1 \\
    & \leq & 15 \\
\end{eqnarray*}

The algorithm answers our first question; given sufficient time, the
monks can finish their task and end the world.

\subsection{A Lower Bound}

We can not yet compute the exact number of steps that the monks need
to move the 64 disks; we can only show an upper bound.  Perhaps---
having pondered the problem since the beginning of time--- the monks
have devised a better algorithm.

In fact, there is no better algorithm, and here is why.  At some step,
we must move the $n$-th disk from the first post to a different post.
For this to happen, the $n-1$ smaller disks must all be stacked out of
the way on the only remaining post.  Arranging the $n-1$ smaller disks
this way requires at least $T_{n-1}$ moves.  After the largest disk is
moved, at least another $T_{n-1}$ moves are required to pile the $n-1$
smaller disks on top.

This argument shows that the number of steps required is at least $2
T_{n-1} + 1$.  Since we gave an algorithm using exactly this number of
steps, we now have a recurrence for $T_n$, the number of moves
required to complete the Tower of Hanoi problem with $n$ disks:

\[
T_n = 2 T_{n-1} + 1
\]

Knowing the $T_1 = 1$, we can use this recurrence to conclude that
$T_2 = 3, T_3 = 7, T_4 = 15, \ldots$.

\subsection{Guess and Verify}

Computing $T_{64}$ from the recurrence would require a lot of work.
It would be nice to have a closed form expression for $T_n$, so that
we could quickly compute the number of steps required to solve the
Towers of Hanoi problem for any given number of disks.  (For example,
we might want to know how much faster moving the disks would be if the
monks donate one of the golden disks to their favorite political party
as ``soft money''.)

There are several different methods for solving recurrences.  The
simplest method is to guess the solution and then to verify that the
guess is correct, usually with an induction proof.  This method is
called ``Guess and Verify'' or ``substitution''.  To help us make an
intelligent guess, we can tabulate $T_n$ for small values of $n$:

\[
\begin{array}{c|c}
n & T_n \\ \hline
1 & 1 \\
2 & 3 \\
3 & 7 \\
4 & 15 \\
5 & 31 \\
\end{array}
\]

From the table, a natural guess is that $T_n = 2^n - 1$.  Whenever you
guess a solution to a recurrence, you should always verify it with a
proof by induction or by some other technique; after all, your guess
might be wrong.  (But why bother to verify in this case?  After all,
if we're wrong, its not the end of the... no, let's check.)

\begin{guess*}
$T_n = 2^n - 1$
\end{guess*}

\begin{verify}
The proof is by induction on $n$.  Let $P(n)$ be the predicate that
$T_n = 2^n - 1$.  In the base case, $P(1)$ is true because $T_1 = 1 =
2^1 - 1$.  In the inductive step, assume $T_n = 2^n - 1$ to prove that
$T_{n+1} = 2^{n+1} - 1$.

\begin{eqnarray*}
T_{n+1} & = & 2 T_n + 1 \\
        & = & 2 (2^n - 1) + 1 \\
        & = & 2^{n+1} - 1
\end{eqnarray*}

The first equality holds by assumption, and the second follows by
application of the induction hypothesis.  The final step is just a
simplification.
\end{verify}

Our guess is now verified.  This shows, for example, that the 7-disk
puzzle will require $2^7 - 1 = 127$ moves to complete.  We can also
now resolve our remaining questions about the 64-disk puzzle.  Since
$T_{64} = 2^{64} - 1$, the monks must complete more than 18 billion
billion steps before the world ends.  Better study for the final.

\subsection{The Plug and Chug Method}

In general, Guess and Verify is the best way to solve a recurrence.
The only problem with the method is guessing the right solution.  In
the Towers of Hanoi example, guessing the solution was easy, but
sometimes the solution has a very strange form that is quite hard to
guess.  Practice helps, of course, but so can some other methods.

Plug and Chug is one such alternative method for solving recurrences.
Plug and Chug is also sometimes called ``expansion'', ``iteration'',
or ``brute force''.  The method consists of four calculation-intensive
steps.  These steps are listed for reference, but will only make real
sense after we work through the Towers of Hanoi example below.

\begin{enumerate}

\item Expand the recurrence equation by alternately ``plugging''
(applying the recurrence equation) and ``chugging'' (simplifying the
resulting expression).

\item Identify a pattern for the recurrence equation after $i$
rounds of plug and chug.  Verify that this pattern is correct by
carrying out one additional round of plug and chug.

\item Substitute a value of $i$ into the pattern so that $T_n$
is expressed as a function of just the first few terms (e.g. $T_1,
T_2, \ldots$).  Substitute computed values for these terms to obtain
an ordinary, non-recurrent expression for $T_n$.

\item Find a closed form for $T_n$ from the ordinary
expression.
\end{enumerate}

The Plug and Chug calculations for the Towers of Hanoi recurrence are
worked out below.

\subsubsection*{Step 1: Plug and Chug}

\begin{eqnarray*}
T_n & = & 1 + 2 T_{n-1} \\
(plug) \quad & = & 1 + 2 (1 + 2 T_{n-2}) \\
(chug) \quad & = & 1 + 2 + 4 T_{n-2}) \\
(plug) \quad & = & 1 + 2 + 4 (1 + 2 T_{n-3}) \\
(chug) \quad & = & 1 + 2 + 4 + 8 T_{n-3} \\
(plug) \quad & = & 1 + 2 + 4 + 8 (1 + 2 T_{n-4}) \\
(chug) \quad & = & 1 + 2 + 4 + 8 + 16 T_{n-4}
\end{eqnarray*}

The first equation is the recurrence that we want to solve.  In the
second step, we transform the original recurrence by {\em plugging};
that is, we apply the recurrence equation to make $T_n$ depend on
earlier terms.  In this case, we eliminate $T_{n-1}$ and make $T_n$
depend on $T_{n-2}$ instead.  Next, we {\em chug}; that is, we
simplify the new expression for $T_n$.  Then we plug again so that
$T_n$ depends on a still earlier term, $T_{n-3}$.  Then we chug and
plug and chug some more.

\subsubsection*{Step 2: Identify and Verify a Pattern}

\begin{eqnarray*}
T_n          & = & 1 + 2 + 4 + \ldots + 2^{i-1} + 2^i T(n-i) \\
(plug) \quad & = & 1 + 2 + 4 + \ldots + 2^{i-1} + 2^i (1 + 2 T_{n-(i+1)}) \\
(chug) \quad & = & 1 + 2 + 4 + \ldots + 2^{i-1} + 2^i + 2^{i+1} T_{n-(i+1)})
\end{eqnarray*}

After enough work, a pattern becomes clear: $T_n$ is always a sum of
consecutive powers of two together with an earlier $T$ term.

The next step is to describe this pattern by writing down the
expression obtained after $i$ rounds of plug and chug.  Then we do one
last round to confirm that the pattern is correct.  This check is very
similar to the inductive step in a proof by induction.

Be careful in the ``chug'' stage; too much simplification can obscure
an emerging pattern.  For example, summing $1 + 2 + 4 + \ldots$ at
every stage would have concealed the geometric series.  The rule to
remember--- indeed, a rule applicable to the whole of college life---
is {\em chug in moderation}.

\subsubsection*{Step 3: Express $n$-th Term Using Early Terms}

\begin{eqnarray*}
T_n & = & 1 + 2 + 4 + \ldots + 2^{i-1} + 2^i T(n-i) \\
T_n & = & 1 + 2 + 4 + \ldots + 2^{n-2} + 2^{n-1} T(1) \\
    & = & 1 + 2 + 4 + \ldots + 2^{n-2} + 2^{n-1}
\end{eqnarray*}

Now we can use the pattern to express $T_n$ as a function of small,
computable terms.  In particular, if we set $i = n - 1$ in the above
pattern, then $T_n$ becomes a function only of $T_1$, which we know is
equal to 1.  This leaves an ordinary, non-recurrent expression for
$T_n$.

\subsubsection*{Step 4: Find a Closed Form for the $n$-th Term}

All that remains is to reduce the ordinary expression for $T_n$ to a
closed form.  We are fortunate in this case, because $T_n$ is the sum
of a geometric series.  We learned how to tackle these before!

\begin{eqnarray*}
T_n & = & 1 + 2 + 4 + 8 + \ldots + 2^{n-2} + 2^{n-1} \\
    & = & \sum_{i=0}^{n-1} 2^i \\
    & = & 2^n - 1
\end{eqnarray*}

We are done!  When using the Plug and Chug method, be sure to go back
and verify that the answer is correct.  It is very easy to make a
mistake when observing the general pattern.


\section{Divide and Conquer Recurrences}

We now turn to another family of recurrences known as \emph{Divide and
  Conquer} recurrences.  These arise in recursive algorithms that
partition their inputs into smaller pieces in order to solve the
problem.


\subsection{The Merge Sort Algorithm}

As a motivating example, we will consider Merge Sort.  There are many
algorithms for sorting a list of $n$ items; in fact, you will see a
dozen of them in 6.046. Merge sort is one of the most popular.

Here is how Merge Sort works.  The input is a list of $n
\geq 1$ items $x_1, x_2, \ldots, x_n$.  If $n = 1$, then the algorithm
returns the single item $x_1$.  If $n > 1$, then the original list is
broken into two lists, $x_1, \ldots, x_{n/2}$ and $x_{n/2+1}, \ldots,
x_n$.  Both of these lists are sorted recursively, and then they are
merged to form a complete, sorted list of the original $n$ items.  All
work is in the merging operation; the details are explained in the
following example.

Suppose we want to sort the list 10, 7, 23, 5, 2, 4, 3, 9.  Since the
number of items is greater than 1, we divide into two lists; one is
10, 7, 23, 5, and the other is 2, 4, 3, 9.  Each list is sorted
recursively.  The results are 5, 7, 10, 23 and 2, 3, 4, 9.

Now we must merge these two small sorted lists into one big sorted
list.  (In this case, the ``small'' lists have 4 items apiece, and the
``big'' list will eventually have 8 items.)  We start with the big
list empty and add one item at a time.  At each step, we compare the
first items in the small lists.  We remove the smaller item and append
it to the end of the big list.  This process repeats until one of the
small lists becomes empty.  At that point, the remaining small list is
appended to the big list and we are done.

For the example, the contents of the three lists after each step are
shown in the table below.

\begin{eqnarray*}
\begin{array}{l|l|l}
small \ list \ 1 & small \ list \ 2 & big \ list \\ \hline
5, 7, 10, 23 & 2, 3, 4, 9 & \\
5, 7, 10, 23 & 3, 4, 9 &  2 \\
5, 7, 10, 23 & 4, 9 & 2, 3 \\
5, 7, 10, 23 & 9 & 2, 3, 4 \\
7, 10, 23 & 9 & 2, 3, 4, 5 \\
10, 23 & 9 & 2, 3, 4, 5, 7 \\
10, 23 & & 2, 3, 4, 5, 7, 9 \\
 & & 2, 3, 4, 5, 7, 9, 10, 23
\end{array}
\end{eqnarray*}

\subsection{Finding a Recurrence}

In the analysis of a sorting algorithm, a traditional question is,
``What is the maximum number comparisons used in sorting $n$ items?''
The number of comparisons is taken as an estimate of the run time.  In
the case of Merge Sort, we can find a recurrence for this quantity.
Solving the recurrence will allow us to study the asymptotic behavior
of the algorithm.

To make the analysis easier, assume for now that the number of items
we are sorting is a power of 2.  This ensures that we can divide the
list of items exactly in half at every stage of the recursion.

Let $T(n)$ be the maximum number of comparisons used by Merge Sort in
sorting a list of $n$ items.  If $n > 1$, then this is equal to the
number of comparisons used in sorting both halves of the list plus the
number of comparisons used in merging the two halves.  

The number of comparisons used in sorting each half of the list is
$T(n/2)$.  Sorting both halves requires $2 T(n/2)$ comparisons.  The
number of comparisons used in merging the two halves is at most $n-1$.
The reason is that one item is appended to the big list after each
comparison, and at least one additional item is appended to the big
list in the final step when one small list becomes empty.  Since the
big list eventually contains $n$ items, there can be at most $n-1$
comparisons.  (Of course, there might be fewer comparisons, but we are
analyzing the worst case.)

Adding all comparisons gives the following recurrence:

\[
T(n) = 2T(n/2) + n - 1
\]

No comparisons are required to sort a list with a single item, so
$T(1) = 0$.  From this fact and the recurrence, we can compute $T(2) =
2T(1) + 2 - 1 = 1$, $T(4) = 2T(2) + 4 - 1 = 5$, $T(8) = 2T(3) + 8 - 1
= 17$, $T(16) = 2T(4) + 16 - 1 = 49$, etc.

\subsection{Solving the Recurrence}

We would like to find a closed form for the number of comparisons used
by Merge Sort in sorting a list of $n$ items.  This requires solving
the recurrence $T(n) = 2T(n/2) + n - 1$.  The first method to try is
Guess and Verify.  The problem is that there is no obvious pattern to
the values from small cases, 0, 1, 5, 17, 49.  Our only other method
is Plug and Chug.  Here we go:

\subsubsection*{Step 1: Plug and Chug}

\begin{eqnarray*}
T(n) & = & n-1 + 2T(n/2) \\
(plug) \quad & = & n-1 + 2(n/2 - 1 + 2T(n/4)) \\
(chug) \quad & = & n-1 + n-2 + 4T(n/4) \\
(plug) \quad & = & n-1 + n-2 + 4(n/4 - 1 + 2T(n/8)) \\
(chug) \quad & = & n-1 + n-2 + n-4 + 8T(n/8) \\
(plug) \quad & = & n-1 + n-2 + n-4 + 8(n/8 - 1 + 2T(n/16)) \\
(chug) \quad & = & n-1 + n-2 + n-4 + n-8 + 16T(n/16)
\end{eqnarray*}

A pattern has emerged.  Note that too much simplification would have
obscured the pattern.

\subsubsection*{Step 2: Identify and Verify a Pattern}

\begin{eqnarray*}
T(n) & = & n-1 + n-2 + \ldots + n-2^{i-1} + 2^iT(n/2^i) \\
(plug) \quad & = & n-1 + n-2 + \ldots + n-2^{i-1} + 2^i(n/2^i - 1 + 2T(n/2^{i+1})) \\
(chug) \quad & = & n-1 + n-2 + \ldots + n-2^{i-1} + n-2^i + 2^{i+1}T(n/2^{i+1}) \\
\end{eqnarray*}

The additional round of plug and chug confirms that the pattern is
correct.

\subsubsection*{Step 3: Express $n$-th Term Using Early Terms}

We must substitute a value for $i$ into the pattern so that $T(n)$
depends on only small terms.  A natural choice is $i = \log_2 n$,
since then $T(n/2^i) = T(1)$.  This substitution makes $T(n)$
dependent only on $T(1)$, which we know is 0.

\begin{eqnarray*}
T(n) & = & n-1 + n-2 + \ldots + n-2^{i-1} + 2^iT(n/2^i) \\
     & = & n-1 + n-2 + \ldots + n-2^{\log_2(n)-1} + 2^{\log_2 n}T(n/2^{\log_2 n}) \\
     & = & n-1 + n-2 + \ldots + n-2^{\log_2(n)-1} + 2^{\log_2 n}T(1) \\
     & = & n-1 + n-2 + \ldots + n-2^{\log_2(n)-1}
\end{eqnarray*}

In the final equation, we used the fact that $T(1) = 0$; this
completely eliminates the last term in the summation.

\subsubsection*{Step 4: Find a Closed-Form for the $n$-th Term}

Now we have an ordinary, non-recurrent expression for $T(n)$.  We can
reduce this to a closed form by summing a series.

\begin{eqnarray*}
T(n) & = & n-1 + n-2 + \ldots + n-2^{i-1} + n-2^{\log_2(n)-1} \\
     & = & \sum_{i=0}^{\log_2(n) - 1} n - 2^i \\
     & = & \sum_{i=0}^{\log_2(n) - 1} n - \sum_{i=0}^{\log_2(n) - 1} 2^i \\
     & = & n \log_2 n - (2^{\log_2 n} - 1) \\ 
     & = & n \log_2 n - n + 1 \\
     & \sim & n \log_2 n
\end{eqnarray*}

What a weird answer--- we never would have guessed this!  To make sure
that there is no error, we can check that the formula gives the same
values for $T(n)$ that we computed earlier:

\[
\begin{array}{c|c}
n & n \log_2 n - n + 1 \\ \hline
1 & 1 \log_2 1 - 1 + 1 = 0 \\
2 & 2 \log_2 2 - 2 + 1 = 1 \\
4 & 4 \log_2 4 - 4 + 1 = 5 \\
8 & 8 \log_2 8 - 8 + 1 = 17 \\
16 & 16 \log_2 16 - 16 + 1 = 49
\end{array}
\]

Sure enough!  Note that the $n \log_2 n$ comparisons used by Merge
Sort are far fewer than the total of $n(n-1)/2$ possible comparisons.

\section{More Recurrences}

Let's compare the Tower of Hanoi and Merge Sort recurrences.

\begin{eqnarray*}
T(n) = 2 T(n-1) + 1 & \quad \quad & T(n) \sim 2^n \\
T(n) = 2 T(n/2) + n - 1 & \quad \quad & T(n) \sim n \log_2 n
\end{eqnarray*}

In the Towers of Hanoi, we divided a problem of size $n$ into two
subproblems of size $n-1$ and did only 1 additional step (moving the
largest disk).  In Merge Sort, we divided a problem of size $n$ into
two subproblems of size just $n/2$, but we did as many as $n-1$
additional steps (merging two sublists).  Which algorithm runs faster?
Merge Sort by a mile!  The key point is that generating smaller
subproblems is far more important than reducing the additional steps
per recursive call.

Let's vary the above recurrences slightly and see how the solutions
change.

\subsection{A Speedy Algorithm}

Suppose we have a speedy algorithm with the best properties of both
earlier algorithms; that is, at each stage the problem is divided in
half {\em and} we do only one additional step.  The run time is
described by the following recurrence:

\begin{eqnarray*}
S(1) & = & 0 \\
S(n) & = & 2 S(n/2) + 1
\end{eqnarray*}

(Another interpretation of this recurrence is that $S(n)$ is the number
recursive calls made when Merge Sort is run on a list of $n$ items.)

Guess and Verify is the first method to try.  (Plug and Chug also
works.)  To motivate a guess, let's tabulate a few values of $S(n)$.
As before, assume that $n$ is a power of two.

\[
\begin{array}{c|c}
n & S(n) \\ \hline
1 & 0 \\
2 & 2S(1) + 1 = 1 \\
4 & 2S(2) + 1 = 3 \\
8 & 2S(4) + 1 = 7
\end{array}
\]

\begin{guess*}
$S(n) = n - 1$
\end{guess*}

\begin{verify}
The proof is by strong induction on $n$.  Let $P(n)$ be the predicate
that if $n$ is a power of two, then $S(n) = n - 1$.  In the base case,
$P(1)$ is true because $S(1) = 0$ by assumption.  In the inductive
step, for $n \geq 2$ assume $P(1)$, $P(2)$, $\ldots$, and $P(n-1)$ to
prove $P(n)$.  If $n$ is not a power of two, then $P(n)$ is vacuously
true.  Otherwise, we have:

\begin{eqnarray*}
S(n) & = & 2 S(n/2) + 1 \\
       & = & 2 (n/2 - 1) + 1 \\
       & = & n - 1
\end{eqnarray*}

The first equation is the recurrence.  The second equality
follows from the induction hypothesis, and the last step is
simplification only.
\end{verify}

The run time of this speedy algorithm is $\sim n$.  This is better
than the $\sim n \log n$ run time of Merge Sort, but only slightly so.
This is consistent with the idea that decreasing the number of
additional steps per recursive call is much less important than
reducing the size of subproblems.

\subsection{A Verification Problem}

Sometimes verifying the solution to a recurrence using induction can
be tricky.  For example, suppose that we have the same recurrence as
before, but we only try to prove that $S(n) \leq n$.  This is true,
but the proof goes awry!

\begin{guess}
$S(n) \leq n$
\end{guess}

{\em Verification (attempt). }
The proof is by strong induction.  Let $P(n)$ be the predicate that if
$n$ is a power of two, then $S(n) \leq n$.  In the base case, $P(1)$
is true because $S(1) = 0 \leq 1$.  In the inductive step, for $n \geq
2$, assume $P(1)$, $P(2)$, $\ldots$, $P(n-1)$ to prove $P(n)$.  If $n$
is not a power of two, then $P(n)$ is vacuously true.  Otherwise, we
have:

\begin{eqnarray*}
S(n)    & = & 2 S(n/2) + 1 \\
        & \leq & 2 (n/2) + 1 \\
        & = & n + 1 \\
        & \not\leq & n
\end{eqnarray*}

The first equation is the recurrence.  The second equality follows by
induction.  The third step is a simplification, and in the fourth step
we crash and burn spectacularly.

We know that the result is true, but the proof did not work!  The
natural temptation is to ease up and try to prove something weaker,
say $S(n) \leq n+1$ or even $S(n) \leq 2n$.  Bad plan!

As was often the case with other induction proofs, the trick is to
choose a {\em stronger} induction hypothesis!  In particular, if we
use the stronger hypothesis that $S(n) \leq n - 1$, then the proof
goes through.  The crux of the argument in the inductive step is shown
below.

\begin{eqnarray*}
S(n)    & = & 2 S(n/2) + 1 \\
        & \leq & 2 (n/2 - 1) + 1 \\
        & = & n - 1 \\
        & \leq & n - 1
\end{eqnarray*}

As before, the first equation is the recurrence, the second follows by
induction, and the third is a simplification.  The final inequality
shows that the induction hypothesis holds for $P(n)$ as desired.

\subsection{A False Proof}

What happens if we try an even stronger induction hypothesis?
Shouldn't the proof work out even more easily?  For example, suppose
our hypothesis is that $S(n) \leq n - 2$.  This hypothesis is false,
since we proved that $S(n) = n - 1$.  But let's see where the proof
breaks.  Here again is the crux of the argument:

\begin{eqnarray*}
S(n)    & = & 2 S(n/2) + 1 \\
        & \leq & 2 (n/2 - 2) + 1 \\
        & = & n - 3 \\
        & \leq & n - 2
\end{eqnarray*}

Something is wrong; we proved a false statement!  The problem is that
we were lazy and did not write out the full proof; in particular, we
ignored the base case.  Since $S(1) = 0 \not\leq -1$, the induction
hypothesis is actually false in the base case.  This is why we cannot
construct a proof with a ``too strong'' induction hypothesis.

\subsection{Altering the Number of Subproblems}
\label{sec:multiples}

Some variants of the Merge Sort recurrence have truly peculiar
solutions!  The main difference in these variants is that we replace
the constant 2 (arising because we create 2 subproblems) by a
parameter $a$.

\begin{eqnarray*}
T(1) & = & 1 \\
T(n) & = & a T(n/2) + n
\end{eqnarray*}

Intuitively, $a$ is the number of subproblems of size $n/2$ generated
at each stage of the algorithm; however, $a$ is actually not required
to be an integer.  This recurrence can be solved by Plug and Chug, but
we will give only the solutions here:

\begin{eqnarray*}
0 \leq a < 2 & \quad & T(n) \sim \frac{2}{2-a}n \\
a = 2 & \quad & T(n) \sim n \log_2 n \\
a > 2 & \quad & T(n) \sim \frac{a}{a-2} n^{\log_2 a}
\end{eqnarray*}

The examples below show that the Merge Sort recurrence is extremely
sensitive to the multiplicative term, especially when it is near 2.

\begin{eqnarray*}
a = 1.99 & \quad & T(n) = \Theta(n) \\
a = 2 & \quad & T(n) = \Theta(n \log n) \\
a = 2.01 & \quad & T(n) = \Theta(n^{1.007\ldots})
\end{eqnarray*}

The constant $1.007\ldots$ is equal to $\log_2 2.01$.


\subsection{A False Theorem}

People often write recurrences with asymptotic notation as in the
previous section, but be careful!  As we have seen before, asymptotic
notation mixed with induction leads to faulty proofs.

\begin{falsethm}
If $T(1) = 1$ and $T(n) = 2 T(n/2) + n$, then $T(n) = O(n)$.
\end{falsethm}

This theorem is false; we know that the correct solution to the
recurrence is $T(n) = \Theta(n \log n)$.

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the predicate that
$T(n) = O(n)$.  In the base case, $P(1)$ is true because $T(1) = 1 =
O(1)$.  In the inductive step, for $n \geq 2$ assume $P(1), P(2),
\ldots P(n-1)$ to prove $P(n)$.  We have:

\begin{eqnarray*}
T(n) & = & 2 T(n/2) + n \\
     & = & 2 O(n/2) + n \\
     & = & O(n)
\end{eqnarray*}

The first equation is the recurrence, the second follows by induction,
and the third is a simplification.
\end{proof}

The general problem is that Big Oh should not be used in an induction
hypothesis.  More specifically, the proof shows that for all $n \geq
1$, $T(n)$ is $O(n)$; that is, $T(1)$ is $O(1)$, $T(2)$ is $O(2)$,
$T(47)$ is $O(47)$, etc.  This is perfectly true, but wholly unrelated
to the theorem statement; it says, in effect, that all constants are
in fact constants.

Recalling the definition of Big Oh notation, the theorem implies that
there exists a constant $c > 0$ and an $n_0$ such that for all $n \geq
n_0$, $|T_n| \leq c n$.  If we pick a $c$ and $x_0$ and then attempt a
proof by induction, then we fail as shown below.

{\em Proof (failed attempt). } The proof is by strong induction.  Let
$P(n)$ be the predicate that $|T_n| \leq c n$.  In the base case,
$P(n_0)$ is true because $T(n_0) \leq cn_0$.  {\em (Suppose that we
chose $c$ large enough to make this true.)} In the inductive step, for
$n \geq n_0 + 1$ assume $P(n_0), \ldots, P(n-1)$ to prove $P(n)$.  We
have:

\begin{eqnarray*}
T(n) & = & 2 T(n/2) + n \\
     & \leq & 2 c (n/2) + n \\
     & = & cn + n \\
     & = & (c + 1) n \\
     & \not\leq & cn
\end{eqnarray*}

The first equation is the recurrence.  The next equality follows by
applying the induction hypothesis.  Thereafter we simplify until the
proof collapses.

\end{document}
% LocalWords:  hanoi Edouard
