\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
%\usepackage{psfig}

\input{macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}

\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1 \textbf{endsoln} \smallskip}

\begin{document}

\tutn{13}{10/28/99}{October 27, 1999}

\begin{problems}

\problem Recall that $F_n$ denotes the $n$th Fibonacci number.

\textbf{False Theorem}:
$F_n = O(1)$.

\begin{proof}
We begin by noting that for all functions $f,g$, 
if $f = O(1)$ and $g=O(1)$, then $f+g = O(1)$.

The proof is by strong induction.  The induction hypothesis, $P(n)$, is
the statement that $F_n = O(1)$.  

\textbf{Base case} $n=1$: $P(n)$ is true because
$F_1 \eqdef 1 = O(1)$.

\textbf{Inductive case}: Suppose $n \geq 1$ and prove $P(n+1)$ assuming
$P(i)$ for all $i \leq n$.   There are two cases.  If $n = 1$, then $F_{n+1}
= F_2 \eqdef 1 = O(1)$.  If $n > 1$, then $F_{n+1} \eqdef F_n + F_{n-1}$.  By
induction hypothesis $F_n = O(1)$ and $F_{n-1} = O(1)$, so as noted above,
$F_n + F_{n-1} = O(1)$.  Hence $F_{n+1} = O(1)$.
\end{proof}

Where is the bug?!

\solution{

The proof is actually a correct proof; the bug is that it proves the wrong
thing.  What is proved that for any \emph{fixed} $n$, the \emph{constant}
$F_n$ is $O(1)$.  This is certainly true---and
uninteresting---because every constant
such as $F_{100}$, or $F_{10^{99}}$, etc., is $O(1)$.  In fact for any
function $f: \naturals \to \naturals$, we have
\begin{equation}\label{fn1}
\forall n [f(n) = O(1)].
\end{equation}
However, this is a very different from the statement that
\begin{equation}\label{f1}
f =O(1),
\end{equation}
where $f$ is the {\em function} defined by the rule that $f(n) \eqdef
F_n$.  Equation~(\ref{f1}) is the proper interpretation of the False
Theorem, and of course it is false.

To clarify the difference between the two statements, we can spell out the
definition of $O()$ notation: equation~(\ref{fn1}) expands to the statement
\[
\forall n \exists c [f(n) \leq c \cdot 1],
\]
and this is trivially true because we can choose different $c's$ for
different $n$'s.  So given $n$, we can simply choose $c$ to be $f(n)$.

On the other hand, equation~(\ref{f1}) expands to the statement
\[
\exists n_0 \exists c \forall n > n_0  [f(n) \leq c \cdot 1].
\]
In this case, the same constant factor $c$ must work for all large enough
$n$.

}


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

\solution{

One such example appeared in Pset 7.  Perhaps a simpler example is
\begin{eqnarray*}
f(n) & \eqdef & 1 + n\cdot \mbox{remainder}(n,2)\\
g(n) & \eqdef & 1 + n\cdot \mbox{remainder}(n+1,2)
\end{eqnarray*}
So on odd $n$, we have $f(n) = n+1$ and $g(n) = 1$, and so no constant
times $g(n)$ will bound $f(n)$ as $n$ ranges over odd numbers.  Therefore,
$\neg[f = O(g)]$.  The situation reverses for even $n$, so also $\neg[g =
O(f)]$.
}

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

\solution{

False: for $i \in \naturals$, let $f_i$ be the constant function defined
by the rule
\[
f_i(n) \eqdef 3^i.
\]
Since each $f_i$ is a constant function, it is true that $f_i = O(1)$ for
each $i$.  Now
\[
\sum_{i=0}^n f_i(n) = \sum_{i=0}^n 3^i = (3^{n+1} - 1)/2,
\]
and $(3^{n+1} - 1)/2$ is not $O(2^n)$.

}

\eparts

\problem

Suppose that there is a type of plant that lives forever, but only
reproduces during the first year of life.  How fast will the plant
population grow?

\solution{

Let $f(n)$ be the number of plants in year $n$.  As boundary
conditions, define $f(0) = 0$ and $f(1) = 1$.  The plant population in
year $n$ is equal to the population from the year before plus the
number of new plants.  The population from the year before is
$f(n-1)$.  The number of new plants this year is equal to the number
of new plants last year or $f(n-1) - f(n-2)$.  We can now form a
recurrence equation for the plant population:

\begin{eqnarray*}
f(n) & = & f(n-1) + (f(n-1) - f(n-2)) \\
     & = & 2 f(n-1) - f(n-2),
\end{eqnarray*}
so
\[
f(n) - 2 f(n-1) + f(n-2)  =  0.
\]
The characteristic polynomial is
\[p(\alpha) \eqdef \alpha^2 - 2 \alpha + 1,
\]
which has the single root $\alpha = 1$ with multiplicity 2.  Therefore,
the solution to the recurrence has the form:
\begin{eqnarray*}
f(n) & = & c_1 \cdot 1^n + c_2 \cdot n \cdot 1^n \\
     & = & c_1 + c_2 \cdot n.
\end{eqnarray*}

The boundary conditions, $f(0) = 0$ and $f(1) = 1$, generate the
following linear equations:
\begin{eqnarray*}
0 & = & c_1 + c_2 \cdot 0, \\
1 & = & c_1 + c_2 \cdot 1.
\end{eqnarray*}
The solution to the equations is $c_1 = 0$ and $c_2 = 1$.
Therefore, the solution to the recurrence is:
\begin{eqnarray*}
f(n) & = & c_1 + c_2 \cdot n \\
     & = & 0 + 1 \cdot n \\
     & = & n
\end{eqnarray*}

The answer turns out to be very simple!  In year $n$, there are exactly
$n$ plants.  Of course, we probably could have solved this problem more
easily by guessing and verifying, but for many other examples, guessing is
not so easy.

}


\end{problems}

\end{document}
