Hi everyone. I am blogging from the Friends Café in downtown Monrovia, CA on a beautiful, chilly day.
Today's blog entry is about to the Fibonacci Sequence and how to find a general formula to generate a sequence.
The Fibonacci Sequence
The world famous Fibonacci Sequence, first introduced by Fibonacci's Liber Abaci, written in 1202, is:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 293, 377...
(Source: Pickover, Clifford. "The Math Book" Sterling Publishing, New York. 2009 - Eddie says: Go get this book - it's awesome!)
It is easy to build the sequence. Start with two entries of 1. Add them up to get the next term. Each subsequent term is the sum of the last two. 1+1=2, 1+2=3, 2+3=5, 3+5=8, 5+8=13, and so on.
We can use this recursion formula:
a_(n+2) = a_(n+1) + a_n
with the initial conditions a_0 = 1 and a_1 = 1.
We can generate a general formula for this.
Technique
Start with the recursion formula:
a_(n+2) = a_(n+1) + a_n
with the initial conditions a_0 = 1 and a_1 = 1.
This is a linear recursion formula. A way to find the general formula is to use a characteristic polynomial. The characteristic polynomial is formed by turning subscripts to exponents (and usually replacing a with another letter, such as x) and finding the roots of the polynomial.
The general formula will have the form
a_n = c_1 * (x_1)^n + c_2 * (x_2)^n + ...
Where n is the number of initial conditions.
In the case of the Fibonacci sequence, we have two initial conditions (a_0 = 1 and a_1 = 1). Hence n=2.
Then use the initial conditions to solve for the c_k constants.
Finding the General Formula
a_(n+2) = a_(n+1) + a_n
with the initial conditions a_0 = 1 and a_1 = 1.
The characteristic equation is:
x^(n+2) = x^(n+1) + x^n
Assuming x ≠ 0, divide both sides by x^n:
x^2 = x + 1
x^2 - x - 1 = 0
The roots of the polynomial are:
x_1 = (1 + √5)/2
x_2 = (1 - √5)/2
Then our general form has:
a_n = c_1 * ((1 + √5)/2)^n + c_2 * ((1 - √5)/2)^n
Our next step is to find c_1 and c_2.
Note when n = 0, a_0 = 1 and:
1 = c_1 + c_2
When n = 1, a_1 = 1 and:
1 = c_1 * (1 + √5)/2 + c_2 * (1 - √5)/2
Leaving us with the system of linear equations:
c_1 + c_2 = 1
c_1 * (1 + √5)/2 + c_2 * (1 - √5)/2 = 1
I like using matrices to solve systems of linear equations, you may a different preferred way, it's all good here:
[ [1, 1], [(1 + √5)/2, (1 - √5)/2] ] * [ [c_1], [c_2] ] = [ [ 1 ], [ 1 ] ]
[ [c_1], [c_2] ] = [ [1, 1], [(1 + √5)/2, (1 - √5)/2] ]^-1 * [ [ 1 ], [ 1 ] ]
[ [c_1], [c_2] ] = [ [(5 - √5)/10, √5/5], [(5 + √5)/10, -√5/5] ] * [ [ 1 ], [ 1 ] ]
which evaluates and simplifies to:
c_1 = (5 + √5)/10
c_2 = (5 - √5)/10
The general formula to generate the Fibonacci sequence is:
a_n = (5 + √5)/10 * ((1 + √5)/2)^n + (5 - √5)/10 * ((1 - √5)/2)^n
An approximate formula would be (8 digits):
a_n ≈ 0.72360680 * 1.6180339^n + 0.27639320 * (-0.6180339)^n
Round off when necessary.
Testing the general formula, find the 2nd and 6th term:
a_2 = (5 + √5)/10 * ((1 + √5)/2)^2 + (5 - √5)/10 * ((1 - √5)/2)^2
a_2 = (5 + √5)/5 + (5 - √5)/2
a_2 = 10/2 = 2
a_6 = (5 + √5)/10 * ((1 + √5)/2)^6 + (5 - √5)/10 * ((1 - √5)/2)^6
a_6 = (65 + 29 * √5)/10 + (65 - 29 * √5)/10
a_6 = 130/10 = 13
A Broader Problem
The technique applied can be applied to the general problem:
a_(n+2) = S * a_(n+1) + T * a_n
With initial conditions a_0 = A and a_1 = B.
Using the trusty HP 50g to assist me, I come up with the following:
a_n = c_1 * (x_1)^n + c_2 * (x_2)^n
where
x_1 = (S + √(S^2 + 4 * T))/2
x_2 = (S - √(S^2 + 4 * T))/2
c_1 = (B - A * x_2)/(x_1 - x_2)
c_2 = (A * x_1 - B)/(x_1 - x_2)
Next time, I am going to look at the general recursion formula:
a_(n+1) = S * a_n + T with the initial condition a_0 = A
I am working a basic programming series, which my target is with the HP 39gii calculator and the series would be posted in March 2013.
Thank you everyone who reads, follows, and comments on this blog. As always it is much appreciated.
Have a great day!
Eddie
This blog is property of Edward Shore. 2013