INDUCTION AND SEQUENCES

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

The Fibonacci sequence is defined as follows:

f_{0} = 0,
f_{1} = 1,
f_{n} = f_{n−1} + f_{n−2} for all n ≥ 2.

This definition lets us compute the sequence iteratively. Thus it begins

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, · · · .

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

τ = \frac{1 + \sqrt{5}}{2},  τ̃ = \frac{1 − \sqrt{5}}{2},

and since these are the roots it follows that

(1)  τ^{2} = τ + 1,  τ^{2} = τ̃ + 1.

A bit of algebra shows that

f_{0} = \frac{τ^{0} − τ^{0}}{\sqrt{5}} , f_{1} = \frac{τ^{1} − τ^{1}}{\sqrt{5}} .

And a bit of algebra combines with the identities (1) to show that

for any n ≥ 2,

if f_{n−1} = \frac{τ^{n−1} − τ^{n−1}}{\sqrt{5}} and f_{n−2} = \frac{τ^{n−2} − τ^{n−2}}{\sqrt{5}}

then consequently f_{n} = \frac{τ^{n} − τ^{n}}{\sqrt{5}} .

It follows by mathematical induction that

for all n ≥ 0, f_{n} = \frac{τ^{n} − τ^{n}}{\sqrt{5}} .

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 int or long quantities for whole numbers and float or 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 τ > 1 while |τ̃| < 1, an approximate formula for the nth Fibonacci number as n gets large is

f_{n} ∼ \frac{τ^{n}}{\sqrt{5}},

and consequently the ratios of consecutive Fibonacci numbers tend to a limit,

lim_{n→∞} \frac{f_{n+1}}{f_{n}} = τ.

The numerically unstable sequence that we discussed in class is defined as follows:

a_{0} = 1,
a_{1} = 0.99,
a_{n} = 100.99a_{n−1} − 99a_{n−2} for all n ≥ 2.

Again the definition lets us compute the sequence iteratively.

It is clear that

a_{0} = (0.99)^{0}, a_{1} = (0.99)^{1}.

And a bit of algebra shows that

for any n ≥ 2,
if a_{n−1} = (0.99)^{n−1} and a_{n−2} = (0.99)^{n−2}
then consequently a_{n} = (0.99)^{n}.

It follows by mathematical induction that

for all n ≥ 0, a_{n} = (0.99)^{n}.

As we saw in class, the Java program to compute this sequence by iteration fails catastrophically.