Linear difference equations with constant coefficients

1. The forward shift operator
Many probability computations can be put in terms of recurrence relations that have to be satisfied by successive
probabilities. The theory of difference equations is the appropriate tool for solving such problems.
This theory looks a lot like the theory for linear differential equations with constant coefficients.
In order to simplify notation we introduce the forward shift operator E , that takes a term u_n and shifts the
index one step forward to u_n+1. We write
Eu_n = u_n+1
E²u_n = EEu_n = Eu_n+1 = Eu_n+2
...
E^ru_n= u_n+r
The general linear difference equation of order r with constant coefficients is

where Φ(E) is a polynomial of degree r in E and where we may assume that the coefficient of E^r is 1.
2. Homogeneous difference equations
The simplest class of difference equations of the form (1) has f (n) = 0, that is simply
Φ((E)u_n = 0.
These are called homogeneous equations.
When Φ(E) = (E−λ₁)(E−λ₂)...(E−λ_r) where the λ_i are constants that are all distinct from each other,
one can prove that the most general solution to the homogeneous equation is
u_n =a₁λ₁ⁿ+ a₂λ₂ⁿ+...+a_rλ_rⁿ
where a₁, a₂,..., a_r are arbitrary constants.
WhenΦ(E) contains a repeated factor (E−λ_a )^h, the corresponding part of the general solution becomes

where n^(k) = n(n−1)(n−2)...(n−k +1) = n!/(n−k)!.
In order to find the n'th term of a linear difference equation of order r, one can of course start by r initial
values , and the solve recursively for any giv en n. Thus, if we want our solution to satisfy certain initial conditions
we may first determine the general solution, and then (if possible) make it satisfy the initial conditions.
There can be no more than r such initial conditions, but they need not (as when we compute the solution
recursively) necessarily be conditions on u₀,... , u_r−1, but can be on any set of r values.
Example 1. Solve u_n+2−u_n = 0.
The equation can be written in the form
(E²−1)u_n = 0
or
(E−1)(E +1)u_n = 0
The general solution is therefore
u_n = a(−1)ⁿ + b1ⁿ
where a, b, c are constants.
Example 2. Find the general solution to the equation
u_n+4 − 9u_n+3 + 30u_n+2 − 44u_n+1 + 24u_n = 0
and hence obtain the particular solution satisfying the conditions
u₀ = 1, u₁ = 5, u₂ = 1, u₃ = − 45.
The equation may be written in the form
(E⁴ −  9E³ + 30E² − 44E + 24)u_n = 0
(E− 2)³(E −  3)u_n = 0.
The general solution is therefore
u_n = 2ⁿ(a + bn + cn(n− 1)) + d3ⁿ
where a, b, c, d are constants.
For the particular side conditions we have
u₀ = a + d = 1,
u₁ = 2a + 2b + 3d = 5
u₂ = 4a + 8b + 8c + 9d = 1
u₃ = 8a + 24b + 48c + 27d =−  45
whence a = 0, b = 1, c = − 2, d = 1, so the particular solution is
u_n = 2nⁿ(3 −  2n) + 3ⁿ.

3. Non-homogeneous difference equations
When solving linear differential equations with constant coefficients one first finds the general solution for
the homogeneous equation, and then adds any particular solution to the non-homogeneous one. The same
recipe works in the case of difference equations, i.e. first find the general solution to
Φ(E)u_n = 0
and a particular solution to
Φ(E) = f (n)
and add the two together for the general solution to the latter equation. Thus to solve these more general
equations, the only new problem is to identify some particular solutions. We will only give a few examples
here, not attempting to treat this problem in any generality.

(i) f (n) = kμ ⁿ, μ ≠ λ_i, i = 1, 2,... , r
In this case one can show that

is a particular solution to Φ(E)u_n = kμ ⁿ. Let namely  Φ(E) =Σa_iEⁱ. Then

Example 3. The general solution of
u_n+2−  5u_n+1 + 6u_n = 3( 4ⁿ)
is u_n = a2ⁿ + b3ⁿ + 4ⁿ where a and b are arbitrary constants.

(ii) f (n) = kμ ⁿ, μ =λ _i, λ _ia non-repeated factor of Φ(E)
In this case a particular solution is given by

where Φ'(μ) denotes

Example 4. The general solution of
u_n+2 −  5u_n+1 + 6u_n = 3( 2ⁿ)
is
where a, b are arbitrary constants.

(iii) f (n) = kμ ⁿ, μ = λ _i,λ _i a repeated factor of Φ(E)
Suppose now that (E  −  λ _i is repeated h times in Φ(E). Then

where n^(k) = n(n  −  1)...(n  −   k +1), is a particular solution of the equation Φ(E) u_n  = kμ ⁿ.

Example 5. The general solution of the equation
(E−2)³(E−3)u_n = 5( 2ⁿ)
is
with a, b, c, d are arbitrary constants

(iv) f (n) is a polynomial in n
First write f as a polynomial in the factorial powers n^(k), so
f (n) = a₀ + a₁ⁿ + a₂^{n(2 )} + ...
Now define the difference operator , by Δu_n = u_n+1− u_n  = (E−1) u_n. Using the symbolic relationship
E = 1 + Δ, we can re-express Φ(E)as Ψ(Δ). Still arguing symbolically , a particular solution is obtained by

provided that we can make any sense out of.The way this will be done is by expanding in powers
of , and using long division . The following rules are needed:
n^(r) = rn^(r−1)
Δ²n^(r) = r^{(2 )}n^(r-2)
...
Δ^k n^(r) = r^(k)n^(r-k)) for k≤r,
= 0 for k > r
and

Example 6. Find a particular solution of the equation
u_n+2-7u_n+1 +12u_n= 3n² + 2n + 2.
First write 3n² + 2n + 2 = 3n^{(2 )} + 5n^{(1 )} + 2 and E² - 7E +12 = (2-Δ )( 3-Δ ). Thus we get

Example 7. Find a particular solution of the equation
u_n+3 - 5u_n+2 + 7u_n+1 - 3u_n = n² + 4n +1.
The required solution is