## 1. The forward shift operator

Many probability computations can be put in terms of recurrence relations that
have to be satisfied by suc-

cessive 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

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 as sume that the
coefficient of E' is 1.
2. Homogeneous difference equations

The simplest class of difference equations of the form (1) has f(n) = 0, that is
simply

These are called homogeneouse quations.

When Φ(E) =(E-λ_{1})(E-λ_{2})...(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

where a_{1},a_{2},...,a_{r} are arbitrary constants.

When Φ(E) contains a repeated factor (E-λ_{α})^{h} ,the corresponding part of the
general solution becomes

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 given 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 μ_{0},... ,μ_{r-1},but can be on any press ion.html">set
of r values .

**Example 1.** Solve μ_{n+2}-μ_{n} = 0.

The equation can be written in the form

or

The general solution is therefore

where a, b, c are constants.

**Example 2**. Find the general solution to the equation

and hence obtain the particular solution satisfying the conditions

The equation may be written in the form

The general solution is therefore

where a, b, c, d are constants.

For the particular side conditions we have

whence a = 0, b =1, c = -2, d =1, so the particular solution is

## 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

and a particular solution to

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 anygenerality.
(i) f(n) = kμ^{n} , μ ≠λ_{i}, i =1, 2,... ,r

In this case one can show that

is a particular solution to Let namely
Then

**Example 3**. The general solution of

is where a and b are arbitrary constants.

**a non-repeated factor of ** Φ(E)

In this case a particular solution is given by

where Φ^{'}(μ) denotes

**Example 4**. The general solution of

is

where a, b are arbitrary constants.

a repeated factor of Φ(E)

Suppose now that (E-λ_{i}) is repeated h times in Φ(E). Then

where is a particular solution of the
equation Φ(E)μ_{n}=kμ^{n
}

**Example 5**. The general solution of the equation

is

with a, b, c, d are arbitrary constants

(iv) f(n) is** a polynomial in** n

First write ƒ as a polynomial in the factorial powers n ^{(k)} ,so

Now define the difference operator , by Using
the symbolic relationship

E=1+Δ we can re-express Φ(E) as Ψ(Δ) Still arguing
symbolically,aparticular solution is obtained by

provided that we can make any sense out of 1/Ψ(Δ) The way this will be
done is by expanding 1/Ψ(Δ)

in powers of Δ and using long division . The fol lowing rules are needed:

Δn^{(r)}=rn^{(r-1)
}

and

**Example 6**. Find a particular solution of the equation

First write Thus we
get

**Example 7**. Find a particular solution of the equation

The required solution is