Mathematics
Recurrence Relations and Their Solutions: The Fibonacci Sequence
Quick fact
The Fibonacci sequence can be described by a simple recurrence (each term is the sum of the two before), yet it also has a closed-form formula—Binet's formula—that uses irrational numbers like √5, and the 100th Fibonacci number can be computed directly without any loop.
Why this is interesting
You’ve likely seen the Fibonacci sequence: 1, 1, 2, 3, 5, 8… But what if you could jump straight to the 100th number without computing all the previous ones?
Read the full explanation
Understanding Recurrence Relations and Their Solutions: The Fibonacci Sequence
A recurrence relation is a way to define a sequence by expressing each term as a function of earlier terms. For the Fibonacci sequence, the rule is: start with F(0)=0 and F(1)=1, then for n≥2, F(n)=F(n−1)+F(n−2). This rule is simple, but to find F(100) you would need to compute all previous terms. That's like climbing a staircase one step at a time. But what if there were an elevator? A closed-form formula, if it exists, gives you a direct expression for F(n) in terms of n alone. For Fibonacci, such a formula exists, and it uses powers of the golden ratio. The key idea is that the recurrence is linear and has constant coefficients, so we can solve it using a characteristic equation. That equation turns the recurrence into an algebra problem: guess that F(n) = r^n, substitute, and find the possible values of r. For Fibonacci, r must satisfy r^2 = r + 1. Solving gives two roots, and the general solution is a combination of powers of those roots. The initial conditions then pin down the exact constants. This method, called the characteristic equation method, works for any linear recurrence with constant coefficients. It shows how algebra can unlock the hidden structure of a sequence.
A deeper explanation
The mechanism behind solving a linear recurrence like Fibonacci's is the characteristic equation. We assume a solution of the form F(n) = r^n. Plugging into F(n) = F(n−1) + F(n−2) gives r^n = r^(n−1) + r^(n−2). Dividing by r^(n−2) yields r^2 = r + 1, or r^2 − r − 1 = 0. The roots are φ = (1+√5)/2 (the golden ratio) and ψ = (1−√5)/2. Because the recurrence is linear and homogeneous, any linear combination of these solutions is also a solution: F(n) = Aφ^n + Bψ^n. Using F(0)=0 and F(1)=1, we solve for A and B, yielding Binet's formula: F(n) = (φ^n − ψ^n)/√5. This closed form is more than a curiosity; it reveals the growth rate (exponential with base φ) and allows direct computation. The characteristic equation method is powerful because it transforms a discrete, recursive problem into an algebraic one, and it generalizes to higher-order recurrences. Moreover, the same recurrence can be represented in matrix form, and matrix exponentiation gives an O(log n) algorithm for computing Fibonacci numbers—crucial in programming contests and cryptography. Understanding this mechanism is foundational for algorithm analysis using recurrences and for generating functions, which offer an alternative algebraic route.