Jonathan. Frech’s WebBlog

Symbolic Closed-Form Fibonacci (#207)

Jonathan Frech

Theoretical Framework

Let $V:=\{(a_j)_{j\in\mathbb{N}}\subset\mathbb{C}|a_n=a_{n-1}+a_{n-2}\forall n>1\}$$V:=\{(a_j)_{j\in\mathbb{N}}\subset\mathbb{C}|a_n=a_{n-1}+a_{n-2}\forall n>1\}$ be the two-di­men­sion­al complex vector space of sequences adhering to the Fibonacci re­cur­rence re­la­tion with basis $B:=((0,1,\dots),(1,0,\dots))$$B:=((0,1,\dots),(1,0,\dots))$.
Let furthermore $f:V\to V,(a_j)_{j\in\mathbb{N}}\mapsto(a_{j+1})_{j\in\mathbb{N}}$$f:V\to V,(a_j)_{j\in\mathbb{N}}\mapsto(a_{j+1})_{j\in\mathbb{N}}$ be the sequence shift endomorphism represented by the transformation matrix

$$A:=M^B_B(f)=\begin{pmatrix}1&1\\1&0\end{pmatrix}.$$$$A:=M^B_B(f)=\begin{pmatrix}1&1\\1&0\end{pmatrix}.$$

By iteratively applying the sequence shift a closed-form solution for the stan­dard Fibonacci sequence follows.

-=-
$$F_n:=(B_1)_n=(f^n(B_1))_1=(A^n\cdot B_1)_2$$$$F_n:=(B_1)_n=(f^n(B_1))_1=(A^n\cdot B_1)_2$$

Diagonalizing $A$$A$ leads to eigenvalues $\varphi=\frac{1+\sqrt{5}}{2}$$\varphi=\frac{1+\sqrt{5}}{2}$, $\psi=\frac{1-\sqrt{5}}{2}$$\psi=\frac{1-\sqrt{5}}{2}$ and a diagonalization

$$A=\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}\psi&\varphi\\1&1\end{pmatrix}\cdot\begin{pmatrix}\psi&0\\0&\varphi\end{pmatrix}\cdot\begin{pmatrix}2\cdot\psi-1&\frac{\varphi+2}{5}\\2\cdot\varphi-1&\frac{\psi+2}{5}\end{pmatrix}.$$$$A=\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}\psi&\varphi\\1&1\end{pmatrix}\cdot\begin{pmatrix}\psi&0\\0&\varphi\end{pmatrix}\cdot\begin{pmatrix}2\cdot\psi-1&\frac{\varphi+2}{5}\\2\cdot\varphi-1&\frac{\psi+2}{5}\end{pmatrix}.$$

Using said diagonalization, one deduces

$$\begin{aligned} A^n\cdot B_1 &=\begin{pmatrix}\psi&\varphi\\1&1\end{pmatrix}\cdot\begin{pmatrix}\psi^n&0\\0&\varphi^n\end{pmatrix}\cdot\begin{pmatrix}2\cdot\psi-1\\2\cdot\varphi-1\end{pmatrix}\\ &=\begin{pmatrix}\psi&\varphi\\1&1\end{pmatrix}\cdot \begin{pmatrix}\psi^n\cdot(2\cdot\psi-1)\\\varphi^n\cdot(2\cdot\varphi-1)\end{pmatrix}\\ &=\begin{pmatrix}\psi^{n+1}\cdot(2\cdot\psi-1)+\varphi^{n+1}\cdot(2\cdot\varphi-1)\\\psi^n\cdot(2\cdot\psi-1)+\varphi^n\cdot(2\cdot\varphi-1)\end{pmatrix}. \end{aligned}$$$$\begin{aligned} A^n\cdot B_1 &=\begin{pmatrix}\psi&\varphi\\1&1\end{pmatrix}\cdot\begin{pmatrix}\psi^n&0\\0&\varphi^n\end{pmatrix}\cdot\begin{pmatrix}2\cdot\psi-1\\2\cdot\varphi-1\end{pmatrix}\\ &=\begin{pmatrix}\psi&\varphi\\1&1\end{pmatrix}\cdot \begin{pmatrix}\psi^n\cdot(2\cdot\psi-1)\\\varphi^n\cdot(2\cdot\varphi-1)\end{pmatrix}\\ &=\begin{pmatrix}\psi^{n+1}\cdot(2\cdot\psi-1)+\varphi^{n+1}\cdot(2\cdot\varphi-1)\\\psi^n\cdot(2\cdot\psi-1)+\varphi^n\cdot(2\cdot\varphi-1)\end{pmatrix}. \end{aligned}$$

Therefore,

$$\begin{aligned} F_n &=(A^n\cdot B_1)_2\\ &=\psi^n\cdot(2\cdot\psi-1)+\varphi^n\cdot(2\cdot\varphi-1)\\ &=\frac{-1}{\sqrt{5}}\cdot\psi^n+\frac{1}{\sqrt{5}}\cdot\varphi^n\\ &=\frac{1}{\sqrt{5}}\cdot(\varphi^n-\psi^n). \end{aligned}$$$$\begin{aligned} F_n &=(A^n\cdot B_1)_2\\ &=\psi^n\cdot(2\cdot\psi-1)+\varphi^n\cdot(2\cdot\varphi-1)\\ &=\frac{-1}{\sqrt{5}}\cdot\psi^n+\frac{1}{\sqrt{5}}\cdot\varphi^n\\ &=\frac{1}{\sqrt{5}}\cdot(\varphi^n-\psi^n). \end{aligned}$$

Thus, a closed-form expression not involving any higher-di­men­sion­al matrices is found.

A Realization in Haskell

To avoid precision errors, I im­ple­ment­ed a basic symbolic expression simplifier (fib.hs) — using $\sqrt[\star]{n}:=\text{sgn}(n)\cdot\sqrt{|n|}\,\forall n\in\mathbb{Z}$$\sqrt[\star]{n}:=\text{sgn}(n)\cdot\sqrt{|n|}\,\forall n\in\mathbb{Z}$ as a negative-capable root, a symbolic expression is modeled as follows.

data Expr = Sqrt Int
          | Neg Expr
          | Expr :+ Expr
          | Expr :* Expr
          | Expr :/ Expr
          | Expr :- Expr
          | Expr :^ Int
          deriving Eq

Said mod­el is capable of representing the above derived formula.

phi   = (Sqrt 1 :+ Sqrt 5) :/ Sqrt 4
psi   = (Sqrt 1 :- Sqrt 5) :/ Sqrt 4
fib n = (Sqrt 1 :/ Sqrt 5) :* (phi :^ n :- psi :^ n)

Using this im­ple­men­ta­tion to calculate the sequence should be possible (assuming the simplifier does not get stuck at any occurring expression), yet takes its sweet time — $F_6$$F_6$ takes half a minute on my 4 GHz ma­chine.

*Main> simplify $ fib 6
\sqrt{64}

More Efficient Fibonacci Calculations

Quicker sequence calculation methods include a brute-force A^n approach, e. g.

import Data.List (transpose)

a *@* b = [[sum . map (uncurry (*)) $ zip ar bc
           | bc <- transpose b] | ar <- a]

a *^* 0 = [[1, 0], [0, 1]]
a *^* n = a *@* (a *^* (n-1))

fib = (!! 0) . (!! 0) . ([[1, 1], [1, 0]] *^*)

as well as using lazy evaluation to construct the whole infinite sequence.

fibs = [0, 1] ++ [x+y | (x, y) <- zip fibs $ tail fibs]