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 cn + 2 = cn + cn + 1, with the initial conditions c0 = 0 and c1 = 1. An interesting thing you can do is to create what is called a generating function

f(t) = Σ cntn

(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, t2, … means they are recoverable). For the Fibonacci sequence, this is

f(t) = 0 + t + t2 + 2t3 + 3t4 + 5t5 + 8t6 + ⋯

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 − tt2)f(t) = t

which of course means f(t) = t/(1 − tt2). 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 − tt2)

f(t) = 5−1/2((1 − φt)−1 − (1 − (1 − φ)t)−1)

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

cn = 5−1/2(φn − (1 − φ)n).

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 r2r − 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φte(1 − φ)t).

This readily gives us a Taylor series:

y = Σ5−1/2(φn − (1 − φ)n)tn/n!.

But we can also solve such differential equations as Taylor series directly. Supposing the solution is of the form y = Σcntn/n! (and every solution indeed has a Taylor series due to theory), we can differentiate this to get y ′ = Σcn + 1tn/n! and y ′ ′ = Σcn + 2tn/n!, and so a solution must satisfy Σ(cn + 2cn + 1cn)tn/n! = 0. That is, the coefficients (excepting the n!’s) satisfy a linear recurrence relation cn + 2 = cn + cn + 1, sort of like the power series case. Every such solution is entirely determined by the values of c0 and c1, 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

cn = 5−1/2(φn − (1 − φ)n).