Scribd
Upload
133 views1 page

Fibonacci Series

The document discusses how Fibonacci numbers can be represented using matrices. It shows that the Fibonacci sequence satisfies the relationship fn=fn-1+fn-2, and can be written as a matrix equation involving multiplying the previous two numbers. By taking powers of this matrix A, its shown the eigenvalues and eigenvectors can be used to derive a closed form solution for the nth Fibonacci number fn as involving the golden ratio. Specifically, fn is approximated as the closest integer to (√5/5)(φn/√2) where φ is (1+√5)/2.

Uploaded by

Anonymous dwt8yNoXm
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
133 views1 page

Fibonacci Series

The document discusses how Fibonacci numbers can be represented using matrices. It shows that the Fibonacci sequence satisfies the relationship fn=fn-1+fn-2, and can be written as a matrix equation involving multiplying the previous two numbers. By taking powers of this matrix A, its shown the eigenvalues and eigenvectors can be used to derive a closed form solution for the nth Fibonacci number fn as involving the golden ratio. Specifically, fn is approximated as the closest integer to (√5/5)(φn/√2) where φ is (1+√5)/2.

Uploaded by

Anonymous dwt8yNoXm
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Fibonacci Numbers and 2 2 matrices R.

Anstee
The fibonacci numbers f1 , f2 , f3 , . . . satify

f1 = 1, f2 = 1 fi = fi1 + fi2 for i = 3, 4, 5, . . .

yielding the sequence 1, 1, 2, 3, 5, 8, 13, 21, . . ..


If we let fn denote the nth fibonacci number we get a matrix equation:
" #" # " #
1 1 fi fi+1
= .
1 0 fi1 fi
" # " #n2 " #
1 1 1 1 1
Thus, if we let A = , we can compute fn as the top entry of =
1 0 1 0 1
" #
1
An2 . To compute a high power of A, we compute the eigenvalues and eigenvectors. Now
1
" #
1k 1
det( ) = k 2 k 1, which has roots k = 1+2 5 and k = 12 5 .
1 0k
" #
1+ 5 1+ 5
eigenvalue: , eigenvector: 2
2 1
" #
1 5 1 5
eigenvalue: , eigenvector: 2 .
2 1
Thus if we let " # " #
1+ 5 1 5 1+ 5
0
P = 2 2 , D= 2
1 5
,
1 1 0 2

we have A = P DP 1 and so At = P DP 1 P DP 1 P DP 1 = P D t P 1 .
#
( 1+2 5 )t
" #" #"
1+ 5 1 5 5 5 5
0
At = P D t P 1 = 2 2
1 5 t
5

5
10

5+ 5
1 1 0 ( 2 ) 5 10

( 55)( 1+2 5)t+1 ( 55 )( 125 )t+1 ( 510 5)( 1+2 5)t+1 + ( 5+105 )( 125 )t+1
" #

=
( 55 )( 1+2 5 )t ( 55 )( 12 5 )t ( 510 5 )( 1+2 5 )t + ( 5+10 5 )( 12 5 )t
" # " # " #
fn n2 1 n1 1
Now using our formula that =A =A , we obtain:
fn1 1 0
! !n ! !n
5 1+ 5 5 1 5
fn =
5 2 5 2
 k
1 5 1 5
Given that 2
.6 and so limk 2
= 0. Thus
! !n
5 1+ 5
fn is the closest integer to
5 2

You might also like