# Symbolic Closed-Form Fibonacci

2018-12-01, post № 207

**Haskell**, **mathematics**, **programming**, #diagonalization

## Theoretical Framework

Let be the two-dimensional complex vector space of sequences adhering to the Fibonacci recurrence relation with basis .

Let furthermore be the sequence shift endomorphism represented by the transformation matrix

By iteratively applying the sequence shift a closed-form solution for the standard Fibonacci sequence follows.

Diagonalizing leads to eigenvalues , and a diagonalization

Using said diagonalization, one deduces

Therefore,

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

## A Realization in Haskell

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

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