# The Fibonacci sequence by way of differential equations

The well-known Fibonacci sequence,

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

`f`(

`t`) = Σ

`c`

_{n}

`t`

^{n}

(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`^{2}, … means they are recoverable). For the Fibonacci
sequence, this is

`f`(

`t`) = 0 +

`t`+

`t`

^{2}+ 2

`t`

^{3}+ 3

`t`

^{4}+ 5

`t`

^{5}+ 8

`t`

^{6}+ ⋯

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`:

`t`−

`t`

^{2})

`f`(

`t`) =

`t`

which of course means `f`(`t`) = `t`/(1 − `t` − `t`^{2}). 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`^{2})

`f`(

`t`) = 5

^{−1/2}((1 −

`φ`

`t`)

^{−1}− (1 − (1 −

`φ`)

`t`)

^{−1})

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}(

`φ`

^{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 `r`^{2} − `r` − 1 has roots
`φ` and (1 − `φ`), so every solution is of the form

`y`=

`A`

`e`

^{φt}+

`B`

`e`

^{(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}(

`φ`

^{n}− (1 −

`φ`)

^{n})

`t`

^{n}/

`n`!.

But we can also solve such differential equations as Taylor series
directly. Supposing the solution is of the form
`y` = Σ`c`_{n}`t`^{n}/`n`! (and every solution indeed has a Taylor series
due to theory), we can differentiate this to get
`y` ′ = Σ`c`_{n + 1}`t`^{n}/`n`! and `y` ′ ′ = Σ`c`_{n + 2}`t`^{n}/`n`!, and so a
solution must satisfy Σ(`c`_{n + 2} − `c`_{n + 1} − `c`_{n})`t`^{n}/`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`_{0} and `c`_{1}, 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}(

`φ`

^{n}− (1 −

`φ`)

^{n}).