Kyle Miller > Mathematics > The Fibonacci sequence by way of differential equations

The Fibonacci sequence by way of differential equations

The well-known Fibonacci sequence,

0, 1, 1, 2, 3, 5, 8, …,

is described by the recurrence relation c_{n + 2} = c_n + c_{n + 1}, with the initial conditions c₀ = 0 and c₁ = 1. An interesting thing you can do is to create what is called a generating function

f(t) = Σ c_ntⁿ

(where the sum is over 0 ≤ n) which is a power series that holds onto a sequence as coefficients (and, basically, linear independence of 1, t, t², … means they are recoverable). For the Fibonacci sequence, this is

f(t) = 0 + t + t² + 2t³ + 3t⁴ + 5t⁵ + 8t⁶ + ⋯

The great thing about writing a sequence in this way is that multiplying the generating function by t shifts it right-ward, inserting a 0 at the beginning. So, we can make use of the fact that each term is the sum of the preceding two to get a simpler characterization of f:

(1 − t − t²)f(t) = t

which of course means f(t) = t/(1 − t − t²). This, by the way, gives rational numbers you can use to amaze and entertain your mathematically-literate friends. For instance, 100/9899 ≈ 0.01010203050813…. But what you can also do is use the partial fraction decomposition of t/(1 − t − t²)

f(t) = 5^−1/2((1 − φt)⁻¹ − (1 − (1 − φ)t)⁻¹)

where φ is the golden ratio, (1 + 5^1/2)/2, and use the power series expansions of these reciprocals to obtain a closed form equation for the Fibonacci sequence, namely

c_n = 5^−1/2(φⁿ − (1 − φ)ⁿ).

While leading recitation for a differential equations course, I realized it’s possible to get this same equation by way of differential equations. What we start with is the homogenous second-order linear differential equation y ′ ′ − y ′ − y = 0, and solve it the normal way (using the characteristic equation), by finding a Taylor series, and then comparing the two solutions. In contrast to above, where the sequence is stored as coefficients to a power series, the sequence will instead be stored as the derivatives of some function. The characteristic polynomial r² − r − 1 has roots φ and (1 − φ), so every solution is of the form

y = Ae^φt + Be^{(1 − φ)t}

for some constants A and B. Because I know where this is going, let’s solve the initial value problem with y(0) = 0 and y ′(0) = 1, which (sparing you the details) gives

y = 5^−1/2(e^φt − e^{(1 − φ)t}).

This readily gives us a Taylor series:

y = Σ5^−1/2(φⁿ − (1 − φ)ⁿ)tⁿ/n!.

But we can also solve such differential equations as Taylor series directly. Supposing the solution is of the form y = Σc_ntⁿ/n! (and every solution indeed has a Taylor series due to theory), we can differentiate this to get y ′ = Σc_{n + 1}tⁿ/n! and y ′ ′ = Σc_{n + 2}tⁿ/n!, and so a solution must satisfy Σ(c_{n + 2} − c_{n + 1} − c_n)tⁿ/n! = 0. That is, the coefficients (excepting the n!’s) satisfy a linear recurrence relation c_{n + 2} = c_n + c_{n + 1}, sort of like the power series case. Every such solution is entirely determined by the values of c₀ and c₁, and these correspond to y(0) and y ′(0), respectively. This means these coefficients form the Fibonacci sequence, and by comparing with the previous solution to the differential equation, we once obtain obtain the following closed-form formula

c_n = 5^−1/2(φⁿ − (1 − φ)ⁿ).