I’m currently preparing a couple of blog posts on measure theory, probability theory and fractals. Since studying, research and writing on these topics is taking quite a long time, I’ve decided to write a small post on the Fibonacci sequence, which showed up when looking at pictures of the now notorious romanesco broccoli. I find it such a cliché to post a picture of that magnificent vegetable when discussing fractals or the Fibonacci sequence, so you’ll have to be happy with a link.
Weirdly enough, the number of spirals on a romanesco is a number from the Fibonacci sequence:
$$\require{physics}
1, 1, 2, 3, 5, 8, 13, 21, \ldots \thinspace ,
$$
but the question I’ll address in this post is the following. For low index numbers $n$ (please note that we start counting at $n=0$, I know, it’s sometimes confusing), it’s relatively easy to determine the corresponding Fibonacci number. For example, for $n=3$, the Fibonacci number is 3, and when $n=7$, the corresponding Fibonacci number is 21. But how do we determine, in general, the $n$-th Fibonacci number?
Since the formula of a sequence can be determined from the roots of its characteristic polynomial, which is in its turn determined from the recursion relation it corresponds to, let’s start by realizing that the Fibonacci sequence satisfies the recursion relation
$$
x_{n+2}
= x_{n+1} + x_{n}
\thinspace ,
$$
which is a linear recursion relation of order 2. The characteristic polynomial of the sequence is therefore
$$
P(z)
= z^2 – z – 1
\thinspace ,
$$
which has roots $\lambda_1$ and $\lambda_2$:
$$
\lambda_1
= \frac{1 + \sqrt{5}}{2}
\qquad \text{and} \qquad
\lambda_2
= \frac{1 – \sqrt{5}}{2}
\thinspace .
$$
Notice that these roots are equal to the golden ratio and its negative inverse, respectively:
$$
\lambda_1 = \varphi
\qqtext{and}
\lambda_2 = -\varphi^{-1}
\thinspace .
$$
The general formula for the $n$-th element of a sequence whose characteristic polynomial has two distinct roots can be written as
$$
x_n
= C_1 \lambda_1^n + C_2 \lambda_2^n
\thinspace ,
$$
where $C_1$ and $C_2$ can be found by solving the linear system of equations
$$
\begin{cases}
x_0 = C_1 + C_2 = 1 \\
x_1 = C_1 \lambda_1 + C_2 \lambda_2 = 1
\thinspace .
\end{cases}
$$
Through the method of substitution, we find that
$$
C_1
= \frac{\sqrt{5} + 1}{2 \sqrt{5}}
\qquad \text{and} \qquad
C_2
= \frac{\sqrt{5} – 1}{2 \sqrt{5}}
\thinspace ,
$$
so the general formula to calculate an element of the Fibonacci sequence is
$$
x_n
= \frac{1}{\sqrt{5}} \qty(
\frac{1 + \sqrt{5}}{2}
)^{n+1}
– \frac{1}{\sqrt{5}} \qty( \frac{1 – \sqrt{5}}{2} )^{n+1}
\thinspace ,
$$
or in terms of the golden ratio:
$$
x_n
= \frac{1}{\sqrt{5}} \qty(
\varphi^{n+1}
– \frac{(-1)^{n+1}}{\varphi^{n+1}}
)
\thinspace .
$$
So, it would take you ages to calculate the 40-th Fibonacci number using its recursion relation, but we can plug in $n=39$ and immediately find
$$
\begin{align}
x_{39} &=
\frac{1}{\sqrt{5}} \qty(
\frac{1 + \sqrt{5}}{2}
)^{40}
-\frac{1}{\sqrt{5}} \qty(
\frac{1 – \sqrt{5}}{2}
)^{40} \\
&= 102.334.155
\thinspace .
\end{align}
$$