Math Explained to Programmers: The Fibonacci Sequence — Difference Equation Approach (Binet)

With mathematic proof explained, step by step.

The story

In calculating the Fibonacci sequence

There are multiple methods to derive this elegant rule. One approach uses matrix transformations, leading to:

From the characteristic roots of the matrix, we obtain the most concise linear form: The Binet Formula.

This approach starts with a difference equation and arrives at the same elegant solution. In this post, we’ll explore the Binet Formula, its derivation, and its ability to solve Fibonacci numbers in O(1).

Difference Equation: Fₙ — Fₙ₋₁ — Fₙ₋₂ = 0

Why is it a second-order linear?

The Fibonacci sequence definition:

can be rewritten as:

This is a “second-order homogeneous linear difference equation”:

• Second-order: It refers to Fₙ₋₂ and Fₙ₋₁ to determine Fₙ
• Linear: Fₙ is a linear combination of previous terms
• Homogeneous: The right-hand side is 0 (no external constants or functions).

Solving the Difference Equation with rⁿ

Similar to solving differential equations, we assume Fₙ = rⁿ, a solution form for homogeneous linear…