Fibonacci Fun

By:

Alex Moore

Many
of us know the Fibonacci sequence, not because of how famous it is, but because
its so easy to remember. To get
the next term in the sequence we simply add the two previous terms. Lets make this more precise. A real sequence is a function from the
nonnegative integers, {0,1,2,3,É}, into the real numbers. Let f be the Fibonacci sequence, that
is, define f(0)=1 and f(1)=1. Then,
given f(0), f(1), É, f(n), we define the Fibonacci sequence recursively as f(n+1)=f(n)+f(n-1). While this sequence is easy to compute,
the terms get large rather quickly.
Below are the first 30 terms of the sequence.

A
natural thing to ask is do the ratio of consecutive terms converge to a
number? Below is the ratio of
terms by use of Excel.

It
seems as though the ratio of terms does not change for n>20. This is good evidence that we have
convergence but this is not a proof.
Let us attempt to prove this converges, and if so, to what number. Let lim denote the limit as n increases
to infinity and let L denote the limit.
Then we have:

L = lim f(n+1)/f(n)=

lim (f(n)+f(n-1))/f(n)=

lim (f(n)/f(n) +
f(n-1)/f(n))=

lim 1+f(n-1)/f(n) =

1 + lim f(n-1)/f(n) =

1+ 1/L.

Therefore,
we know the limit of the ratios satisfies the equation L = 1 + 1/L. By multiplying the equation by L we get
L^{2} = L+1 which is the same as L^{2} –L-1=0. This is another famous
equation. The roots of this
equation are r and 1-r, where r is the golden ratio

r = ½ +sqrt(5)/2.

Clearly
f(n+1)/f(n) is greater than 0 since f(n+1) = f(n) + f(n-1) > f(n) and so our
limit is r since 1-r <0. What
is we took the ratio of every second term, that is, f(n+2)/f(n) ? Do these ratios converge? If so, to what number does it
converge? Let us get an idea of
the behavior. Column 4 is the
ratio of each second term.

Once
again it appears that these ratios are converging since the ratios for n>22
do not appear to be changing. Let
us follow the same procedure as before. Let L be the limit.

L = lim f(n+2)/f(n) =

lim (f(n+1)+f(n))/f(n) =

lim f(n+1)/f(n) + f(n)/f(n)
=

lim f(n+1)/f(n) +1 =

1 + lim f(n+1)/f(n) =

1+r.

Using
the result from above we see that the limit is 1+r! This is interesting.
Suppose we let L_{k} be the limit of the ratio of every k^{th}
term, that is L_{k} = lim f(n+k)/f(n). Then,

L_{k+1} = lim
f(n+(k+1))/f(n) =

lim (f(n+k)+f(n+k-1))/f(n) =

lim f(n+k)/f(n) +
f(n+k-1)/f(n) =

lim f(n+k)/f(n) + lim
f(n+k-1)/f(n) =

L_{k} + L_{k-1}.

Wow! These limits follow a similar structure
that the Fibonacci sequence follows!
Is this surprising? It
probably should not be but it is neat!
Is there a nice closed form for these numbers? Lets see:

L_{1} = r

L_{2} = 1+r

L_{3} = L_{2}
+ L_{1} = 1+2r

L_{4} = L_{3}
+ L_{2} = 2+3r

L_{5} = L_{4}
+ L_{3} = 3+5r

The
pattern appears to be following L_{k} = f(k-2) + r f(k-1)!

The
final aspect of this sequence we will look at is: is there a closed (possibly
continuous) function g(x) such that f restricted to the nonnegative integers is
the Fibonacci sequence? That is,
is there a function f(x) such that g(n)=f(n) for all nonnegative integers n?
Yes! By use of eigenvector and
eigenvalue methods of linear algebra we have the formula

g(x) = (r^{x+1} -
(1-r)^{x+1})/sqrt(5).

What
does the graph of this horrendous function g(x) look like? Since there is a limiting constant of
the ratios I would expect that the graph to look similar to h(x) = r^{x}. Lets look!

This
graph certain does have the look of an exponential graph, just as we expected!