Difference equations are very much analogous to differential equations. Difference equations are more elementary, but differential equations are more familiar.
It seems odd to use a more advanced thing to explain a simpler thing, like saying a quartet is a symphony orchestra with only four instruments. But if for some reason you managed to become familiar with orchestras before learning what a quartet is, this explanation would be helpful.
Differential equations are a standard part of the curriculum for science and engineering students, but difference equations are not. And not without reason: differential equations are a prerequisite for future courses but difference equations are not. But if a curriculum were to include difference equations and differential equations, it might make sense to teach the former first because the topic is more tangible.
To illustrate the similarity between the two topics, this post will solve the difference equation [1]
Fn+2 = Fn+1 + Fn
and the differential equation
y” = y‘ + y
The difference equation defines the Fibonacci numbers, with one set of initial conditions, and the Lucas numbers with different initial conditions. The differential equation is analogous in ways we’ll see below.
Both equations are solved by assuming the form of the solution with a free parameter. Two values of the parameter will be found via a quadratic equation,giving two independent solutions. All solutions are linear combinations of these two solutions.
Difference equation example
The Fibonacci numbers start with F0 = 0 and F1 = 1. From there it’s obvious that F2 = 1, F3 = 2, and so forth.
The Lucas numbers start with L0 = 2 and L1 = 1. From there we see L2 = 3, L4 = 4, etc.
Bootstrapping the solution starting from initial conditions is trivial. However, this does not give us a general expression for the solution, and it does not let us explore the solutions of the difference equation for all initial conditions.
So let’s go back and solve the difference equation first, then apply initial conditions, analogous to what one typically does for ordinary differential equations.
Assume solutions have the form Fn = xn for some x to be determined. Then
xn+2 – xn+1 – xn = 0
for all non-negative n and so
x² – x – 1 = 0
and the two roots are the golden ratio
ϕ = (1 + √5)/2
and its complement
1 – ϕ = (1 – √5)/2.
So the general solution to the recurrence relation
Fn+2 = Fn+1 + Fn
is
Fn = aϕn + b(1 – ϕ)n
for constants a and b to be determined by initial conditions. For the Fibonacci numbers, a = 1/√5 and b = –a. For the Lucas numbers, a = b = 1.
Our assumption of the form of the solution is justified because it worked. There can’t be any other solutions of another form because clearly the initial conditions determine the third element of the sequence, and the second and third elements determine the fourth, etc.
Differential equation example
Assume solutions have the form y = exp(kt) for some k to be determined. Sticking this into the differential equation shows
k² exp(kt) – k exp(kt) – exp(kt) = 0
and so
k² – k – 1 = 0.
This is the same equation as above, and so the roots are ϕ and 1 – ϕ. The general solution is
y(t) = a exp(ϕt) + b exp((1-ϕ)t)
where the constants a and b are determined by the initial value of y and y‘.
It’s not as clear in this case that we’ve found all the solutions and that our solution is unique given initial conditions, but it’s true.
Related posts
[1] Someone might object that this is a recurrence relation and not a difference equation: each term is defined in terms of its predecessors, but not in terms of function differences. But you could rewrite the equation in terms of differences.
If ΔFn = Fn – Fn-1 then we can rewrite our equation as Δ² F – 3ΔF + F = 0.