Symbolic Closed-Form Fibonacci

Let V := \{(a_j)_{j\in\mathbb{N}}\subset\mathbb{C}|a_n=a_{n-1}+a_{n-2}\forall n>1\} be the two-dimensional complex vector space of sequences adhering to the Fibonacci recurrence relation with basis 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}} be the sequence shift endomorphism represented by the transformation matrix

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 standard Fibonacci sequence follows.

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

Diagonalizing A leads to eigenvalues \varphi = \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}.

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}

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}

Thus a closed-form expression not involving any higher-dimensional matrices is found.


To avoid precision errors, I implemented a basic symbolic expression simplifier (fib.hs) — using \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 model 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 implementation 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 takes half a minute on my 4 GHz machine.

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

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]
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.