Intro Video Intro Video

The Fibonacci Numbers \(Fn\) form a sequence of integers defined by the recurrence formula: \[F_n = F_{n-1} + F_{n-2} \] and the starting values \(F_0 := 0, F_1:= 1\). Thus, \(F_2 = F_0+F_1 = 1\), \(F_3 = 2\), \(F_4 = 3\), etc…

This same function can be written as: \[F_n=\frac{φ^{n+1}+(\frac{-1}{φ})^{n-1}}{1+φ^2}\] \[φ = \frac{1+\sqrt{5}}{2}\] In this project we study the behavior of the Fibonnaci Secuence and its relationship to the famous Golden Ratio \(φ\), and explain how we can derive the second function from the first using tools we have learned in the class.

The following R code shows both the recursive function definition for the Fibonacci Sequence fib(n) and the polynomial fibBeta(n):

fib <- function(n){
  if(n <= 0){
    return(0)
  }else if(n == 1){
    return(1)
  }else{
    return(fib(n-1) + fib(n-2))
  }
}

fibBeta <- function(n){
  phi <- (1+sqrt(5))/2  #compute golden ratio and negative inverse
  invertPhi <- -1/phi
  return( (phi**(n+1) + invertPhi**(n-1))/(1+phi*phi) )
}

fibList <- function(x, fn){
  return(unlist(lapply(x, fn)))
}

startNums <- 1:20
fibNums <- fibList(startNums, fib)
fibBetaNums <- fibList(startNums, fibBeta)
cat(startNums, sep = " ")
## 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
cat(fibNums, sep = " ")
## 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
cat(fibBetaNums, sep = " ")
## 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

What’s the difference between them?

library(microbenchmark)
times <- microbenchmark(
  fibList(1:20, fib),
  fibList(1:20, fibBeta)
)
times
## Unit: microseconds
##                    expr       min        lq        mean     median
##      fibList(1:20, fib) 47577.286 49935.264 53556.36673 51063.2065
##  fibList(1:20, fibBeta)    50.424    57.378    76.12714    75.8895
##          uq      max neval
##  52911.7580 94207.90   100
##     83.7075   174.37   100
plot(times, ylab="time (microseconds)")

The Golden Ratio

\[φ = \frac{1+\sqrt{5}}{2}\] The ratio between suceeding Fibonnaci numbers tends towards \(φ\). This can be mathematically explained by the following limit: \[\lim_{n\to\infty} \frac{F_n}{F_{n-1}}\]

We can visualize how quickly the ratio tends towards this perfect number in the graph below.

plot( fibList(2:21, fibBeta)/fibList(1:20, fibBeta) ~ startNums,xlab="", sub="The gold line is the golden ratio\nAs you can see, the ratio of Fn/Fn-1 tends towards that line.", ylab="Fn / Fn-1")
lines( fibList(2:21, fibBeta)/fibList(1:20, fibBeta) ~ startNums)
abline(a=((1+sqrt(5))/2), b=0, col="gold")

Linear Algebra Connection

In order to put this formula into linear algebra, we must find a matrix we can multiply recursively in order to achieve the result.

Given that \(F_0:=0, F_1:=1\), we can start with a base matrix of \(F_{(1,0)}:=\begin{bmatrix}1\\ 0\end{bmatrix}\).

We are trying to calculate \(F_{(n , n-1)}:=\begin{bmatrix}F_n\\ F_{n-1}\end{bmatrix}\) via multiplying a matrix \(A\) by \(F_{(1,0)}\),

Given a matrix \(A := \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}\) we can calculate \(F_{(2 , 1)}\) via the operation \[AF_{(1,0)} = F_{(2,1)} = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}1\\ 0\end{bmatrix} = \begin{bmatrix}1\\ 1\end{bmatrix}\]

We can continue this process to yield the next number \(F_{(3 , 2)}\): \[AF_{(2,1)} = F_{(3,2)} = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}1\\ 1\end{bmatrix} = \begin{bmatrix}2\\ 1\end{bmatrix}\]

This process can be generalized by the formula: \[AF_{(n-1,n-2)} = F_{(n,n-1)} = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}F_{n-1}\\ F_{n-2}\end{bmatrix} = \begin{bmatrix}F_n\\ F_{n-1}\end{bmatrix}\]

\[A^nF_{(1,0)} = F_{(n+1,n)}\]

Interestingly, the eigen values of \(A\) are both \(φ\) and \(\frac{-1}{φ}\).

A <- data.frame(c(1,1),c(1,0)) #Create the vector A
A
##   c.1..1. c.1..0.
## 1       1       1
## 2       1       0
eigA <- eigen(A)
eigA$values     #Eigen Values of A 
## [1]  1.618034 -0.618034
phi <- (1+sqrt(5))/2  #compute golden ratio and negative inverse
invertPhi <- -1/phi

c(phi,invertPhi) == eigA$values  # Compute to see if eigen values and golden ratios are equivalent
## [1] TRUE TRUE

I wonder if the matrix \(Q\) which we derive from the diagonalization of \(A\) has any special properties…

Given the Eigen Matrix: \[U:= \begin{bmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\ 1 & 1\end{bmatrix}\] And its inverse: \[U^{-1}:= \frac{1}{\sqrt{5}}\begin{bmatrix} 1 & \frac{-1+\sqrt{5}}{2} \\ -1 & \frac{1+\sqrt{5}}{2}\end{bmatrix}\] We can find the diagonalized matrix \(Q\) from \(A\) with the following formula: \[Q=U^{-1}AU=\begin{bmatrix} \frac{1+\sqrt{5}}{2} & 0 \\ 0 & \frac{1-\sqrt{5}}{2}\end{bmatrix}\] Notation: \[A^nF_{(1,0)} = F_{(n+1,n)}\]

We can also use \(Q\) to prove:

\[A^n = UQ^nU^{-1} = \frac{1}{1+φ^2}\begin{bmatrix} φ^{n+2}+(\frac{-1}{φ})^n & φ^{n+1}+(\frac{-1}{φ})^{n-1}\\ φ^{n+1}+(\frac{-1}{φ})^{n-1} & φ^{n}+(\frac{-1}{φ})^{n-2}\end{bmatrix}\]

Given

\[A^nF_{(1,0)} = F_{(n+1,n)}\] \[\begin{bmatrix}F_{n+1}\\F_n \end{bmatrix} = A^n\begin{bmatrix}1\\ 0\end{bmatrix} = \frac{1}{1+φ^2}\begin{bmatrix} φ^{n+2}+(\frac{-1}{φ})^n \\ φ^{n+1}+(\frac{-1}{φ})^{n-1}\end{bmatrix}\]

Therefore

\[F_n=\frac{φ^{n+1}+(\frac{-1}{φ})^{n-1}}{1+φ^2}\]

startNums <- 1:20
cat(startNums, sep = " ")
## 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
cat(fibNums, sep = " ")
## 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
cat(fibBetaNums, sep = " ")
## 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765