Fibonacci Numbers

There are various problems that play with the Fibonacci numbers, so we need to look into these as well. They form a series and are defined like this:

Definition: Fibonacci Numbers

The Fibonacci numbers for them infinite natural number sequence $(F_i{)}_i$ which is defined as

$$F_1:=1F_2:=1,F_n:=F_{n-2}+F_{n-1}.$$

Efficient computation

Although the definition is recursive, one shouldn't compute them in a recursive way. Otherwise one will have to recompute terms that one had computed before and end up with an $\mathcal{O}(2^n)$ complexity to compute the $F_n$.

Example: Let's compute $F_4$. Then we have the following recursive expansion:

• $F_4$
• $F_2+F_3$
• $(F_0+F_1)+(F_1+F_2)$
• $(F_0+F_1)+(F_1+(F_0+F_1))$

You can see that we need to compute $F_2$ twice and look up $F_0$ twice, $F_1$ three times. When we would compute $F_5$ in this way, we would have to compute $F_3$ and $F_4$ again.

Iterative generation

It is much better to use an iterative algorithm:

• Set $a:=0$, $b:=1$.
• Iterate …
  • Yield $b$.
  • Set $c:=a+b$.
  • Set $a:=b$.
  • Set $b:=c$.

This will yield 1, 1, 2, 3, 5, … as we want.

It never recomputes any number. Therefore the complexity here is $\mathcal{O}(n)$ for a specific $F_n$, and $\mathcal{O}(1)$ per number in the sequence. If one needs to iterate through the Fibonacci numbers, this is the algorithm of choice.

Computation in O(log n)

If we want to compute $F_n$ in isolation, we would have to iterate up to the desired $n$. Computing a specific $F_n$ can be made more efficient:

Theorem: n-th Fibonacci Number by Exponentiation

$F_n$ and $F_{n+1}$ can be computed in $\mathcal{O}(\log n)$ by using

$$\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)={\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)}^n\left(\begin{array}{c}0\\ 1\end{array}\right)$$

together with exponentiation by squaring.

Proof

The above iterative algorithm can also be expressed in matrix form:

$$\left(\begin{array}{c}a\\ b\end{array}\right):=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)$$

We can apply this matrix over and over in order to advance in the algorithm. Hence we can write a closed-form expression:

$$\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)={\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)}^n\left(\begin{array}{c}0\\ 1\end{array}\right)$$

The exponentiation of the matrix would be $\mathcal{O}(n)$ naively, but with exponentiation by squaring, one can do this in $\mathcal{O}(\log n)$ steps.

Eigenvalue trick for O(1)

There is an eigenvalue trick that one can use to directly compute any Fibonacci number in closed form:

Theorem: n-th Fibonacci Number via Eigenvalues

The $n$-th Fibonacci number is

$$F_n=-\frac{\beta }{\sqrt{5}}({\alpha }^{n+1}+{\beta }^{n+1}),\text{where}\alpha :=\frac{1+\sqrt{5}}{2},\beta :=\frac{1-\sqrt{5}}{2}.$$

Proof

We start with the closed-form expression from the other theorem:

$$\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)={\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)}^n\left(\begin{array}{c}0\\ 1\end{array}\right)$$

We will do an eigensystem decomposition of the matrix in order efficiently compute its exponentiation. Let's call the matrix in the middle $M$. We can find its eigenvalues

$${\lambda }_1=\frac{1+\sqrt{5}}{2},{\lambda }_2=\frac{1-\sqrt{5}}{2}.$$

The associated eigenvectors are

$$v_1=\left(\begin{array}{c}\frac{\sqrt{5}-1}{2}\\ 1\end{array}\right),v_2=\left(\begin{array}{c}-\frac{\sqrt{5}+1}{2}\\ 1\end{array}\right).$$

We collect these into an eigenvalue matrix $\mathrm{\Lambda }$ and an eigenvector matrix $V$:

$$\mathrm{\Lambda }=\left(\begin{array}{cc}\frac{1+\sqrt{5}}{2}& 0\\ 0& \frac{1-\sqrt{5}}{2}\end{array}\right),V=\left(\begin{array}{cc}\frac{\sqrt{5}-1}{2}& -\frac{\sqrt{5}+1}{2}\\ 1& 1\end{array}\right).$$

Hence we can write the matrix $M$ using the eigensystem as

$$M=V\mathrm{\Lambda }{V}^{-1}.$$

The inverse of $V$ is

$$V^{-1}=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}1& \frac{\sqrt{5}+1}{2}\\ -1& \frac{\sqrt{5}-1}{2}\end{array}\right).$$

Putting all of that together gives us

$$\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)=(V\mathrm{\Lambda }{V}^{-1}{)}^n\left(\begin{array}{c}0\\ 1\end{array}\right).$$

The real simplification comes from writing out $(V\mathrm{\Lambda }{V}^{-1}{)}^n$ and realizing that $V^{-1}V=1$. Then we can simplify

$$(V\mathrm{\Lambda }{V}^{-1}{)}^n=V{\mathrm{\Lambda }}^n{V}^{-1}.$$

Because $\mathrm{\Lambda }$ is a diagonal matrix, applying the power to the matrix is the same as applying the power to the elements on the diagonal.

We can then plug in all the expressions and we arrive at

$$\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\frac{\sqrt{5}-1}{2}& -\frac{\sqrt{5}+1}{2}\\ 1& 1\end{array}\right)\left(\begin{array}{cc}{\left(\frac{1+\sqrt{5}}{2}\right)}^n& 0\\ 0& {\left(\frac{1-\sqrt{5}}{2}\right)}^n\end{array}\right)\left(\begin{array}{cc}1& \frac{\sqrt{5}+1}{2}\\ -1& \frac{\sqrt{5}-1}{2}\end{array}\right)\left(\begin{array}{c}0\\ 1\end{array}\right).$$

As we're only interested in $F_n$ and not $F_{n+1}$, it is sufficient to use the first row of $V$. Then we can introduce the shorthands $\alpha$ and $\beta$. After executing the matrix multiplications, we arrive at the claimed formula.

This expression doesn't work well numerically as one has to project high powers of an irrational number (the $\sqrt{5}$) back onto an integer. Eventually, even 64-bit floating point will be insufficient as they lack both the precision to faithfully represent the whole number. They will return inf results.

Numerical approximation

We can work with the logarithm to make it more tractable.

Theorem

The $n$-th Fibonacci number approximately is

$$\log (F_n)\approx \log (-\frac{\beta }{\sqrt{5}})+(n+1)\log (\alpha ).,\text{where}\alpha :=\frac{1+\sqrt{5}}{2},\beta :=\frac{1-\sqrt{5}}{2}.$$

Proof

We have $|\alpha |>1$ and $|\beta |<1$. For large $n$, ${\beta }^{n+1}\to 0$ and we can neglect this. Then we apply the logarithm to both sides and get the desired result.