Math Explained to Programmers: The Fibonacci Sequence- Using fast doubling approach

The Story

Today, let’s explore an efficient way to compute Fibonacci numbers using the Fast Doubling Method, which is based on the properties of the Fibonacci sequence.

The Recurrence Relation

The Fibonacci sequence is defined by the recurrence relation:

F(n + 2) = F(n + 1) + F(n)

Addition Formula for Fibonacci Numbers

An important property of the Fibonacci sequence is:

F(m + n) = F(m + 1)·F(n) + F(m)·F(n - 1)

This addition formula is the foundation of the Fast Doubling Method. Let’s prove it step by step.

Proof of Fibonacci Addition Formula

Base Case:

When n=1:

F(m + 1) = F(m + 1)·F(1) + F(m)·F(0)

Since F(1)=1 and F(0)=0, the equation holds.

Assume for some n, the formula holds:

F(m + n) = F(m + 1)·F(n) + F(m)·F(n - 1)

To prove it for n+1:

F(m + (n + 1)) = F(m + n + 1)

Using the Fibonacci recurrence F(n+1)=F(n)+F(n−1), we write (1):

F(m + n + 1) = F(m + n) + F(m + n - 1)