NOTES FOR SECOND YEAR DIFFERENCE AND
DIFFERENTIAL EQUATION
PART II: DIFFERENCE EQUATIONS
1. Definitions
Recall that a finite sequence has the form {yn }N
n=0 and an infinite sequence has
∞
the form {yn }n=0 . A difference equation of order m has the form
(1) yn+m = F (n, yn , yn+1 , . . . , yn+m−1 ),
where F is a given function. In general, our task will be to solve the initial value
problem
(2) yn+m = F (n, yn , yn+1 , . . . , yn+m−1 ), y0 = c + 0, y1 = c1 , . . . , ym−1 = cm−1
for a given right hand side F . Notice that we should assign m initial conditions
for a difference equation of order m. Another way to think of this is to say that
when we’re picking solutions of a difference equation of order m, we must make m
choices (each of which is an initial condition). In this way, we should imagine the
space of solutuons to (1) as being m-dimensional. For instance,
n
1
yn+1 = nyn , yn+1 = yn
2
are both difference equations of order 1, i.e. first order difference equations. It
might be instructive to stop reading right now and write out the first several terms
of both of these sequences, if we take y0 = 1.
A solution to a difference equation is a sequence of number {yn }∞ n=0 such that
yn+m = F (n, yn , yn+1 , . . . , yn+m )
for all n = 0, 1, 2, 3, . . .
Difference equations come in several different varieties, which we start to list
now. If the index n does not appear in the formula for F , then we call the equation
autonomous; otherwise it is non-autonomous. If F is a linear function in the
variables yn , yn+1 , . . . , yn+m−1 , then we say the difference equation is linear, and
otherwise we say it is nonlinear. Notice that a linear difference equation need not
be linear in the n variable. For instance,
1
yn+2 = + yn − yn+1
n2
Date: 2013.
1
,is a linear, second order, non-autonomous difference equation. A linear difference
equation has coefficients in front of each of its terms, which can either be con-
stant (with respect to the index n), or variable (i.e. nonconstant). Finally, if the
sequence {yn = 0}∞ n=0 is a solution to the difference equation, then we say it is
homogeneous, and otherwise we say it is non-homogeneous. Notice that all of
these descriptions of the difference equation depend only on the function F , and
make no reference at all to the initial value y0 .
One of the main themes we will see is that linear difference (and differential)
equations are much easier to solve than nonlinear equations. In fact, we will see
that we can often write down solutions to linear difference equations, very explicitly,
whereas we often have no hope of writing out an explicit solution to a nonlinear
difference equation. This phenomenon persists to differential equations.
2. Some basic examples
It will be worthwhile to consider some examples before we continue. You’re
already familar with the arithmetic and geometric sequences from MAM1000. A
sequence of numbers {yn }∞ n=0 is arithmetic if the difference yn+1 −an = d is the same
for all n. For instance, if d = 2 and y0 = 0 we obtain the sequence of non-negative
even integers:
y0 = 0, y1 = 2, y2 = 4, y3 = 6, · · · , yn = 2n, · · · .
This sequence is a solution to the difference equation
yn+1 = yn + 2
with the initial condition y0 = 0. In this way, we can say the sequence {0, 2, 4, 6, . . . }
solves the initial value problem
yn+1 = F (n, yn ) = yn + 2, y0 = 0.
This is a linear, first order, non-homogeneous, autonomous difference equation with
constant coefficients.
A sequence {yn }∞ n=0 is geometric if the ratio yn+1 /yn = r is the same for all n.
For instance, the sequence
1 1 1 1
y0 = 1, y1 = , y2 = , y3 = , · · · , yn = n , · · ·
2 4 8 2
is a geometric sequence with common ratio r = 1/2. We can recognize this sequence
as a solution to the initial value problem
1
yn+1 = F (n, yn ) = yn , y0 = 1.
2
This is a linear, first order, homogeneous, autonomous difference equation with
constant coefficients.
Another example you may have seen before is the Fibonacci sequence, which
solves the intial value problem
yn+2 = F (n, yn , yn+1 ) = yn + yn+1 , y0 = y1 = 1.
2
, The first several terms of the solution are
y0 = y1 = 1, y2 = 2, y3 = 3, y4 = 5, y5 = 8, y6 = 13, y7 = 21, y8 = 34, y9 = 55, y10 = 89, . . .
This is a linear, second order, homogeneous, autonomous difference equation with
constant coefficients. We see that the terms of the Fibonacci sequence grow very
rapidly.
Here are some more complicated examples of difference equations. The equation
yn+2 = F (n, yn , yn+1 ) = yn yn+1
is second order, nonlinear, homogeneous, and autonomous. The equation
1
yn+1 = F (n, yn ) = yn2
n
is first order, nonlinear, non-autonomous, and homogeneous. The equation
yn+2 = F (n, yn , yn+1 ) = n − yn yn+1 .
is second order, nonlinear, non-autonomous, and non-homogeneous. It can be much
more difficult to solve an initial value problem for these latter difference equations!
3. First order, linear, constant coefficient difference equations
We will begin with the simplest difference equations: those which are first order,
linear, with constant coefficient. We can write the general form of this difference
equation as
(3) yn+1 = F (n, yn ) = ayn + g(n),
where a is a constant and g is a function. We will first treat the case g(n) = 0 for
all n; this is the autonomous and homogeneous case. Then we have a geometric
sequence, which we can compute explicitly.
Proposition 1. Let a and c be real numbers with a 6= 0. The solution to the initial
value problem
(4) yn+1 = F (n, yn ) = ayn , y0 = c
n
is yn = ca . On the other hand, if a = 0 then the solution to the same initial value
problem is y0 = c, and yn = 0 for n ≥ 1.
Observe that, regardless of what a is, the trivial sequence {yn = 0}∞
n=0 is the
solution to the initial value problem with c = 0.
Proof. We use induction. Suppose that we already know
y0 = c, y1 = ca, y2 = ca2 , . . . , yn = can
and we wish to find yn+1 . Then by our difference equation we have
yn+1 = ayn = a(can ) = can+1 ,
which satisfies our rule. Since we already have y0 = c (the base case of our induc-
tion), this completes the proof.
We pause here to notice some key differences between solutions, depending on a.
3
DIFFERENTIAL EQUATION
PART II: DIFFERENCE EQUATIONS
1. Definitions
Recall that a finite sequence has the form {yn }N
n=0 and an infinite sequence has
∞
the form {yn }n=0 . A difference equation of order m has the form
(1) yn+m = F (n, yn , yn+1 , . . . , yn+m−1 ),
where F is a given function. In general, our task will be to solve the initial value
problem
(2) yn+m = F (n, yn , yn+1 , . . . , yn+m−1 ), y0 = c + 0, y1 = c1 , . . . , ym−1 = cm−1
for a given right hand side F . Notice that we should assign m initial conditions
for a difference equation of order m. Another way to think of this is to say that
when we’re picking solutions of a difference equation of order m, we must make m
choices (each of which is an initial condition). In this way, we should imagine the
space of solutuons to (1) as being m-dimensional. For instance,
n
1
yn+1 = nyn , yn+1 = yn
2
are both difference equations of order 1, i.e. first order difference equations. It
might be instructive to stop reading right now and write out the first several terms
of both of these sequences, if we take y0 = 1.
A solution to a difference equation is a sequence of number {yn }∞ n=0 such that
yn+m = F (n, yn , yn+1 , . . . , yn+m )
for all n = 0, 1, 2, 3, . . .
Difference equations come in several different varieties, which we start to list
now. If the index n does not appear in the formula for F , then we call the equation
autonomous; otherwise it is non-autonomous. If F is a linear function in the
variables yn , yn+1 , . . . , yn+m−1 , then we say the difference equation is linear, and
otherwise we say it is nonlinear. Notice that a linear difference equation need not
be linear in the n variable. For instance,
1
yn+2 = + yn − yn+1
n2
Date: 2013.
1
,is a linear, second order, non-autonomous difference equation. A linear difference
equation has coefficients in front of each of its terms, which can either be con-
stant (with respect to the index n), or variable (i.e. nonconstant). Finally, if the
sequence {yn = 0}∞ n=0 is a solution to the difference equation, then we say it is
homogeneous, and otherwise we say it is non-homogeneous. Notice that all of
these descriptions of the difference equation depend only on the function F , and
make no reference at all to the initial value y0 .
One of the main themes we will see is that linear difference (and differential)
equations are much easier to solve than nonlinear equations. In fact, we will see
that we can often write down solutions to linear difference equations, very explicitly,
whereas we often have no hope of writing out an explicit solution to a nonlinear
difference equation. This phenomenon persists to differential equations.
2. Some basic examples
It will be worthwhile to consider some examples before we continue. You’re
already familar with the arithmetic and geometric sequences from MAM1000. A
sequence of numbers {yn }∞ n=0 is arithmetic if the difference yn+1 −an = d is the same
for all n. For instance, if d = 2 and y0 = 0 we obtain the sequence of non-negative
even integers:
y0 = 0, y1 = 2, y2 = 4, y3 = 6, · · · , yn = 2n, · · · .
This sequence is a solution to the difference equation
yn+1 = yn + 2
with the initial condition y0 = 0. In this way, we can say the sequence {0, 2, 4, 6, . . . }
solves the initial value problem
yn+1 = F (n, yn ) = yn + 2, y0 = 0.
This is a linear, first order, non-homogeneous, autonomous difference equation with
constant coefficients.
A sequence {yn }∞ n=0 is geometric if the ratio yn+1 /yn = r is the same for all n.
For instance, the sequence
1 1 1 1
y0 = 1, y1 = , y2 = , y3 = , · · · , yn = n , · · ·
2 4 8 2
is a geometric sequence with common ratio r = 1/2. We can recognize this sequence
as a solution to the initial value problem
1
yn+1 = F (n, yn ) = yn , y0 = 1.
2
This is a linear, first order, homogeneous, autonomous difference equation with
constant coefficients.
Another example you may have seen before is the Fibonacci sequence, which
solves the intial value problem
yn+2 = F (n, yn , yn+1 ) = yn + yn+1 , y0 = y1 = 1.
2
, The first several terms of the solution are
y0 = y1 = 1, y2 = 2, y3 = 3, y4 = 5, y5 = 8, y6 = 13, y7 = 21, y8 = 34, y9 = 55, y10 = 89, . . .
This is a linear, second order, homogeneous, autonomous difference equation with
constant coefficients. We see that the terms of the Fibonacci sequence grow very
rapidly.
Here are some more complicated examples of difference equations. The equation
yn+2 = F (n, yn , yn+1 ) = yn yn+1
is second order, nonlinear, homogeneous, and autonomous. The equation
1
yn+1 = F (n, yn ) = yn2
n
is first order, nonlinear, non-autonomous, and homogeneous. The equation
yn+2 = F (n, yn , yn+1 ) = n − yn yn+1 .
is second order, nonlinear, non-autonomous, and non-homogeneous. It can be much
more difficult to solve an initial value problem for these latter difference equations!
3. First order, linear, constant coefficient difference equations
We will begin with the simplest difference equations: those which are first order,
linear, with constant coefficient. We can write the general form of this difference
equation as
(3) yn+1 = F (n, yn ) = ayn + g(n),
where a is a constant and g is a function. We will first treat the case g(n) = 0 for
all n; this is the autonomous and homogeneous case. Then we have a geometric
sequence, which we can compute explicitly.
Proposition 1. Let a and c be real numbers with a 6= 0. The solution to the initial
value problem
(4) yn+1 = F (n, yn ) = ayn , y0 = c
n
is yn = ca . On the other hand, if a = 0 then the solution to the same initial value
problem is y0 = c, and yn = 0 for n ≥ 1.
Observe that, regardless of what a is, the trivial sequence {yn = 0}∞
n=0 is the
solution to the initial value problem with c = 0.
Proof. We use induction. Suppose that we already know
y0 = c, y1 = ca, y2 = ca2 , . . . , yn = can
and we wish to find yn+1 . Then by our difference equation we have
yn+1 = ayn = a(can ) = can+1 ,
which satisfies our rule. Since we already have y0 = c (the base case of our induc-
tion), this completes the proof.
We pause here to notice some key differences between solutions, depending on a.
3
