A more interesting way to find nth Fibonacci number.

Fibonacci sequence is a prime example in teaching recursion to newcomers, and a great opportunity to brag if your language supports Tail Call Optimization, but it often goes unnoticed that there is a closed-form expression which lets us find the nth Fibonacci number with great ease and in much faster way. This article will present the expression, and explain -step by step- its derivation using high-school mathematics.

Here is the expression (for \( u_1 = u_2 = 1 \) ):

\[ u_n = \frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{2}\right)^n\right) \]

Derivation of the Closed-Form Expression

Find a closed-form expression for \( u_{n+2} = u_{n+1} + u_n \) for \( u_1 = u_2 = 1 \).

Let \( u_n = c \times k^n \) for some constants \(c\) and \(k\). Now substitute this into the recurrence relationship:

\[ \begin{aligned} u_{n+2} &= u_{n+1} + u_n \\c \times k^{n+2} &= c \times k^{n+1} + c \times k^n \end{aligned} \]

Let’s simplify the expression by eliminating \(c\) and \(k^n\):

\[ \begin{aligned} c \times k^{n+2} &= c \times k^{n+1} + c \times k^n \\c \times k^{n+2} &= c \times \left( k^{n+1} + k^n \right) \\k^{n+2} &= k^{n+1} + k^n \\k^2 &= k + 1 \end{aligned} \]

Using quadratic formula to solve \( k^2 - k - 1 = 0 \), we would find:

\[ k = \frac{1 \pm \sqrt 5}{2} \]

Hence it seems there are two possible solutions:

\[ u_n = c \times \left(\frac{1 + \sqrt 5}{2}\right)^n \]

or

\[ u_n = c \times \left(\frac{1 - \sqrt 5}{2}\right)^n \]

Let’s try to find \(c\) by using the predefined values \( u_1 = u_2 = 1 \), starting with the first possible solution:

\[ \begin{aligned} u_1 &= 1 = c \times \left(\frac{1 + \sqrt 5}{2}\right) \\ u_2 &= 2 = c \times \left(\frac{1 + \sqrt 5}{2}\right)^2 \end{aligned} \]

It’s clear that two sets of equations are inconsistent, that is, there is no value of \(c\) that can satisfy both equations. It would be also true for the second possible solution we found (though omitted to keep the article concise).

Another thing we can try is to use both solutions we found by substituting them into the recurrence relation itself:

\[ u_n = c_1 \times \left(\frac{1 + \sqrt 5}{2}\right)^n + c_2 \times \left(\frac{1 - \sqrt 5}{2}\right)^n \]

Now if we try again for \( u_1 = u_2 = 1 \):

\[ \begin{aligned} u_1 &= 1 = c_1 \times \left(\frac{1 + \sqrt 5}{2}\right) + c_2 \times \left(\frac{1 - \sqrt 5}{2}\right) \\ u_2 &= 1 = c_1 \times \left(\frac{1 + \sqrt 5}{2}\right)^2 + c_2 \times \left(\frac{1 - \sqrt 5}{2}\right)^2 \end{aligned} \]

Solving two equations simultaneously, we would find \( c_1 = \frac{1}{\sqrt 5} \) and \( c_2 = - \frac{1}{\sqrt 5}\). Hence, our closed-form expression is:

\[ \begin{aligned} u_n &= \frac{1}{\sqrt 5} \times \left(\frac{1 + \sqrt 5}{2}\right)^n - \frac{1}{\sqrt 5} \times \left(\frac{1 - \sqrt 5}{2}\right)^2 \\ u_n &= \frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{2}\right)^n\right) \end{aligned} \]

Testing the Closed-Form Expression and Comparison With the Recursive Calculation

I used Python 3.6.1 x64 on Windows 10 x64 to perform the following benchmarks using the code below:

# Recursive version
def fib_r(n: int) -> int:
    return 1 if n >= 2 else fib_r(n - 1) + fib_r(n - 2)

# Closed-form version
def fib_cf(n: int) -> int:
    return 0.4472135954999579 * (1.618033988749895**n - (-0.6180339887498949)**n)

The closed-form version hold accurate for \(n < 72\) and is off-by-one when \(n = 72\). This is clearly because of the computational limits in handling floating-point numbers. 72 is not a magic number either, but 72nd Fibonacci number is equal to 498,454,011,879,264 which contains 15 significant digits, and all the constants in fib_cf(n) have 16 significant digits, hence some loss in accuracy is expected considering that the last digits of those constants are rounded off. For instance in Python \(\sqrt 2\) will give you 1.4142135623730951 while it is actually 1.4142135623730950488….

As Michael Abrash said, “The Best Optimizer Is between Your Ears”. =)

Interesting Reading

Edsger W. Dijkstra - In honour of Fibonacci (EWD654)
Dr Ron Knott - A Formula for the n-th Fibonacci number