\documentclass[10pt]{amsart}

\newcommand{\lra}{\longrightarrow}
\newcommand{\Z}{{\mathbf Z}}
\newcommand{\Q}{{\mathbf Q}}
\newcommand{\R}{{\mathbf R}}
\newcommand{\C}{{\mathbf C}}
\newcommand{\Proj}{{\mathbf P}}
\newcommand{\northpole}{{\mathbf n}}
\renewcommand{\Re}[1]{{\text Re}(#1)}
\renewcommand{\Im}[1]{{\text Im}(#1)}

\include{xy}
\xyoption{all}
\SelectTips{cm}{}
\CompileMatrices

\include{iJSepsf}
\newcommand{\graphillus}[3]{\epsfysize=#1truein
\vbox{\centerline{\epsffile{#2.eps}}\caption{#3}}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}

\begin{document}

\title{Induction and Sequences}
\maketitle

This handout is to follow up on some ideas from lecture.

\medskip

The {\em Fibonacci sequence} is defined as follows:
\begin{align*}
f_0&=0,\\
f_1&=1,\\
f_n&=f_{n-1}+f_{n-2}\quad\text{for all $n\ge2$}.
\end{align*}
This definition lets us compute the sequence iteratively.  Thus it begins
$$
0,\quad1,\quad1,\quad2,\quad3,\quad5,\quad8,\quad13,\quad21,\quad34,
\quad55,\quad89,\quad144,\quad\cdots.
$$
A closed form expression for the Fibonacci number~$f_n$ involves the roots of
the polynomial
$$
X^2-X-1.
$$
By the quadratic formula, the roots are
$$
\tau=\frac{1+\sqrt5}2,\qquad\widetilde\tau=\frac{1-\sqrt5}2,
$$
and since these are the roots it follows that
\begin{equation}\label{ga}
\tau^2=\tau+1,\qquad\widetilde\tau^2=\widetilde\tau+1.
\end{equation}
A bit of algebra shows that
$$
f_0=\frac{\tau^0-\widetilde\tau^0}{\sqrt5},\qquad
f_1=\frac{\tau^1-\widetilde\tau^1}{\sqrt5}.
$$
And a bit of algebra combines with the identities~\eqref{ga} to show that
\begin{align*}
&\text{\em for any $n\ge2$,}\\
&\text{{\em if $f_{n-1}=\frac{\tau^{n-1}-\widetilde\tau^{n-1}}{\sqrt5}$
and $f_{n-2}=\frac{\tau^{n-2}-\widetilde\tau^{n-2}}{\sqrt5}$}}\\
&\text{{\em then consequently
$f_n=\frac{\tau^n-\widetilde\tau^n}{\sqrt5}$.}}
\end{align*}
It follows by mathematical induction that
$$
\text{\em for all $n\ge0$,\quad
$f_n=\frac{\tau^n-\widetilde\tau^n}{\sqrt5}$.}
$$
You might enjoy writing a Java program to compute Fibonacci numbers iteratively
and again using the closed form expression, and compare the results.  You will
need to use {\tt int} or {\tt long} quantities for whole numbers
and {\tt float} or {\tt double} quantities for floating-point numbers.

One comment to be made here is that the mathematical induction argument is
not very satisfying: it tells us nothing about how on earth we ever
found the closed form for~$f_n$ in the first place.  The induction only
verifies that the formula, apparently given to us by oracle, works.

Another comment is that the closed form does not make it all obvious that
the Fibonacci numbers are integers.

A third comment is that since $\tau>1$ while $|\widetilde\tau|<1$, an
approximate formula for the $n$th Fibonacci number as $n$ gets large is
$$
f_n\sim\frac{\tau^n}{\sqrt5},
$$
and consequently the ratios of consecutive Fibonacci numbers tend to a limit,
$$
\lim_{n\to\infty}\frac{f_{n+1}}{f_n}=\tau.
$$

\medskip

\medskip

The numerically unstable sequence that we discussed in class
is defined as follows:
\begin{align*}
a_0&=1,\\
a_1&=0.99,\\
a_n&=100.99a_{n-1}-99a_{n-2}\quad\text{for all $n\ge2$}.
\end{align*}
Again the definition lets us compute the sequence iteratively.

It is clear that
$$
a_0=(0.99)^0,\qquad a_1=(0.99)^1.
$$
And a bit of algebra shows that
\begin{align*}
&\text{\em for any $n\ge2$,}\\
&\text{{\em if $a_{n-1}=(0.99)^{n-1}$ and $a_{n-2}=(0.99)^{n-2}$}}\\
&\text{{\em then consequently $a_n=(0.99)^n$.}}
\end{align*}
It follows by mathematical induction that
$$
\text{\em for all $n\ge0$,\quad
$a_n=(0.99)^n$.}
$$
As we saw in class, the Java program to compute this sequence by iteration
fails catastrophically.

\end{document}
