Fibonacci on Crack

LinearAlgebra

• In my last post Top 5 2x2 matrices ranked, the Fibonacci matrix was able to calculate the usual Fibonacci pattern $F_n=F_{n-1}+F_{n-2}$. However, we only examined one recursive sequence. What if I told you, you could do this for any pattern possible!

Lucas Numbers and creating your own sequence

• The classical Fibonnaci sequence starts at 0, 1. However, this property can hold for any sequence you want. Suppose you wanted to start with the numbers 2 and 1. then your initial vector will be $\left[\begin{array}{c}2\\ 1\end{array}\right]$. If we apply the same technique, we will generate the following sequence : $2,1,3,4,7,11,...$. this sequence is called the Lucas Numbers.

Facts about the Lucas Numbers

$$\begin{array}{r}\begin{array}{cccccc}1& 1& 2& 3& 5& 8\\ 2& 1& 3& 4& 7& 11\end{array}\end{array}$$

Tribonacci sequence:

• The Tribonacci sequence is a little different, where instead of adding two numbers, you add three numbers. Lets suppose the first three numbers of the sequence are $0,0,1$. The Tribonacci sequence would look like $0,1,1,2,4,7,15,...$ and our recursive formula would look like $F_n=F_{n-1}+F_{n-2}+f_{n-3}$ Hence, our base case would be $\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]$ and our transformation would be of the form

$$\begin{array}{r}\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]\end{array}$$

Why use a matrix?

While the matrix approach to any n-th Fibonacci sequence is tedious, it does provide a clever way to compute Fibonacci numbers in a quicker speed than a naive approach. When you tell a computer to calculate an n-th Fibonacci number, it will take n steps to do it. With computers, we can divide and conquer the matrix multiplication, resulting in only taking log(n) steps!

Final Facts. The Golden Ratio!

• Take our 2x2 matrix used for finding the Fibonacci numbers. Now evaluate its eigenvalues

Step By step guide of solving it $\lambda$ such that

$$\begin{array}{r}\det \left|\left[\begin{array}{cc}0-\lambda & 1\\ 1& 1-\lambda \end{array}\right]\right|=0\end{array}$$

Hence,

$$\begin{array}{rl}(0-\lambda )(1-\lambda )-(1)(1)& =0\\ {\lambda }^2-\lambda -1& =0\end{array}$$

Using which every method of your choosing to solve a quadratic, we get that

$$\begin{array}{r}\lambda =\frac{1\pm \sqrt{5}}{2}\end{array}$$

• Look closely to one of the Eigenvalues. ITS THE GOLDEN RATIO! $\varphi =\frac{1+\sqrt{5}}{2}$

Fibonacci ain't Done

$$\begin{array}{r}\underset{n\to \infty }{\lim }\frac{F_n}{F_{n-1}}=L\end{array}$$ $$\begin{array}{rl}\underset{n\to \infty }{\lim }\frac{F_n}{F_{n-1}}& =\underset{n\to \infty }{\lim }\frac{F_{n-1}+F_{n-2}}{F_{n-1}}\\ & =\underset{n\to \infty }{\lim }1+\frac{F_{n-2}}{F_{n-1}}\\ & =\underset{n\to \infty }{\lim }1+\frac{1}{L}\end{array}$$

We then arrive to the following:

$$\begin{array}{r}L=1+\frac{1}{L}⟺L^2-L-1=0\end{array}$$

Giving us the same quadratic!

• In the end, the Fibonacci Sequence seems to revolve around the golden ratio and it being a root to the polynomial : $x^2-x-1=0$

More Resources and Questions to the audience

• This post reaches many different aspects of the Fibonacci sequence, and its various oddities, but it gets even more convoluted! When examining the relationships between n-th Fibonacci sequence and their polynomials. I will describe a new notion, the Fibonacci Polynomial to describe the polynomial of the following form : $${\mathbb{P}}_n=\begin{array}{r}{x}^n-(\sum _{k=1}^{n-1}{x}^k)=0\end{array}$$

$\{x_2,x_3,...\}$, where $x_i$ is the positive root of ${\mathbb{P}}_n$. For example, $x_2=\varphi$, the golden ratio. Does this sequence converge? Does it converge to 2?

Suppose we have a sequence

This question spawned from this post I was reading the other day

https://math.stackexchange.com/questions/4098306/how-does-the-tribonacci-sequence-have-anything-to-do-with-hyperbolic-functions

• Anyways, thanks for reading my rabbit hole into the recursive nature of the Fibonacci sequence, and with the nature of recursive functions, they are always mysteriously magical and AWESOME!