Objectives of This Lesson:

• To explore linear discrete dynamical systems of order 2 with your calculator.

• To develop methods for finding the general and particular solutions to a second-order linear discrete dynamical systems.

• To examine the stability and long-term behavior of solutions to a second-order homogeneous discrete dynamical system.

Nearly all of the discrete dynamical systems examined in detail up to this lesson have been dynamical systems of order 1. In this lesson, we examine the second-order discrete dynamical systems:

(I) a₀=b₀, a₁=b₁
(R) a_n=f(a_n-1, a_n-2, n)

that are linear; that is, systems for which the recurrence relation (R) can be written as
a_n=ha_n-1+ka_n-2+g(n)

for some constants h and k, and g(n) is a given function of n. The first part of this lesson will deal with such systems that are also homogeneous; that is, for which g(n)=0 for all n.

Example 4.1: Consider the discrete dynamical system

(I) a₀=0, a₁=1
(R) a_n=2a_n-1-a_n-2 for n>1

Note here that we have to give two initial values to get the recurrence relation started. Further, the computation of the values for the successive terms always involves reaching back and operating on two previous values. The values for this system can be calculated by hand as follows:

n	an
0	0
1	1
2	2(1) – 0 = 2
3	2(2) – 1 = 3
4	2(3) – 2 = 4
5	2(4) – 3 = 5

Looking at the values, it appears that this system might have the solution a(n)=n for all n. We shall check this out later in the lesson.

In many ways, the solution process for homogeneous discrete dynamical systems of order 2 parallels that for systems of order 1. These latter systems were systems in which the new term was some multiple of the previous term:

(I) a₀ = c
(R) a_n = ra_n-1 for n>0

We saw that the solution for this system can be written as a(n)=crⁿ for all n.

Suppose that we look for solutions of the form

(*) a(n)=a_n=crⁿ

to a homogeneous recurrence relation

(**) a_n=ha_n-1+ka_n-2

of order 2. By substitution, you can see that (*) will be a solution of (**) provided that r satisfies:

crⁿ = hcr^n-1 + kcr^n-2

Rewrite the preceding equation in the form

crⁿ - hcr^n-1 - kcr^n-2 = cr^n-2(r²-hr-k) = 0

This means that:

If r is any root of the quadratic equation
(C) x²-hx-k = 0

then a(n)=a_n=crⁿ is a solution of the homogeneous recurrence relation

(R) a_n = ha_n-1+ka_n-2

of order 2.

The quadratic equation (C) is called the characteristic equation of the recurrence relation (R).

If we solve the characteristic equation, we may get two distinct real roots, r and s that play the role played by the ratio r in the first-order recurrence relation and solution. A conjecture for a solution to this second-order homogeneous system of order 2 might be

a(n) = c₁rⁿ + c₀sⁿ for all n

where r and s are the distinct real roots to the characteristic equation and c₁ and c₀ are constants derivable from the recurrence relation and initial values.

The solution in this case, like in the first-order cases, is a function that must satisfy the original dynamical systems’ defining recurrence relation. In this case, evaluating the solution for a(n), a(n – 1), and a(n – 2) gives the values:

a(n) = c₁rⁿ + c₀sⁿ; a(n–1) = c₁r^n–1 + c₀s^n–1; and a(n–2) = c₁r^n–2 + c₀s^n–2. Substituting these expressions back into the recurrence relation we have:

c₁rⁿ + c₀sⁿ = h(c₁r^n–1 + c₀s^n–1) + k(c₁r^n–2 + c₀s^n–2).

If we simplify this equation, we find that it can be written as:

c₁r^n–2(r² – hr – k) + c₀s^n–2(s² – hs – k) = 0.

But this relationship will be identically equal to 0 for all values of n if and only if both r² – hr – k and s² – hs – k are identically equal to 0 for all values of n. Hence, we would want to choose r and s such that they are the roots to the quadratic equation x² – hx – k = 0, the characteristic equation associated with the homogeneous dynamical system of order 2 that we started with above. We will show later that if r and s are distinct real roots of the characteristic equation, all solutions of the system can be written in this form.

Summary:
If r and s are distinct real roots of the characteristic equation
(C) x²-hx-k=0

for a second order, homogeneous recurrence relation

(R) a_n=ha_n-1+ka_n-2 for n>0,

then

a(n)=c₁rⁿ+c₂sⁿ

is the general solution of the equation, where c₁ and c₂ are constants determined by initial values.

Example 4.2: Solve the discrete dynamical system

(I) F₀ = 1, F₁ = 1
(R) F_n = F_n-1 + F_n-2 for n>1

that defines the Fibonacci sequence
{ F_n } = { 1,1,2,3,5,8,13,21,34,... }

Solution: The characteristic equation for the system is

x²-x-1 = 0

which has roots

r1 = (1+51/2)/2

r2 = (1-51/2)/2

Therefore, the general solution of the recurrence relation (R) is
F(n) = c₁[(1+5^1/2)/2]ⁿ + c₂[(1-5^1/2)/2]ⁿ

Now impose the initial conditions F₀=1 and F₁=1 to obtain the equations:

1 = c₁ + c₂
1 = c₁(1+5^1/2)/2 + c₂(1-5^1/2)/2

The preceding equations can be solved for c₁, c₂ to obtain the following solution for the Fibonacci system

F(n) = (1/2(5)^1/2)[(1+5^1/2)/2]ⁿ⁺¹ - (1/2(5)^1/2)[(1-5^1/2)/2]ⁿ⁺¹

F(n) = (1/2ⁿ⁺¹5^1/2)[(1+5^1/2)ⁿ⁺¹ -(1-5^1/2)ⁿ⁺¹]

Although it does not look very likely that this formula for F(n) will produce the Fibonacci sequence 1,1,2,3,5,8,13,..., you can check it on your calculator. For example, if you enter this formula into your calculator, the following tables of values will result.

Right on the money!

The homogeneous discrete dynamical system of order 2 studied at the beginning of this lesson:

(I) a₀=0, a₁=1
(R) a_n=2a_n-1-a_n-2 for n>1

has the characteristic equation
x²-2x+1 = 0

This equation can be written as

(x-1)² = 0

so it has a double root x=1. This means that

a_n = c₁1ⁿ

is a solution of the recurrence relation (R) of the system for any choice of the constant. However, no choice of c₁ will yield the initial values

a₀=0, a₁=1.

Notice that a second solution of this recurrence relation can be obtained by multiplying this first solution by n; that is

a_n = c₂n 1ⁿ

is also a solution! To see this, just substitute this expression into the recurrence relation a_n = 2a_n-1 - a_n-2:

c₂n 1ⁿ = 2c₂(n-1)1^n-1 - c₂(n-2)1^n-2
c₂n = 2c₂n - 2c₂ - c₂n + 2c₂
c₂n = c₂n : It checks!

This means that

a_n = a(n) = c₁1ⁿ + c₂n 1ⁿ

is a general solution of the recurrence relation

a_n = 2a_n-1 - a_n-2 for n>1

for any choice of constants c₁ and c₂.

Now impose the initial conditions:

0 = a₀ = c₁1⁰ + c₂(0) (1ⁿ) = c₁
1 = a₁ = c₁1¹ + c₂(1) (1¹) = c₁ + c₂

Thus, c₁=0 and c₂=1, so the solution of the given discrete dynamical system is

a(n) = 1ⁿ + (n)(1ⁿ) = n for all n

This squares with the tabular information that we developed earlier.

The method used in the preceding example to construct the general solution actually always works:

If a homogeneous recurrence relation

a_n = ha_n-1 + ka_n-2

of order 2 has a characteristic equation:

x²-hx-k = 0

with a double root x=r, then the general solution of the recurrence relation is

a(n) = a_n = c₁rⁿ + c₂nrⁿ

where c₁ and c₂ are constants that are determined by the initial conditions.

The heart of the proof of the preceding result is showing that, if x=r is a double root of the characteristic equation

x²-hx-k = 0

then a_n=c₂nrⁿ satisfies the recurrence relation:

a_n = ha_n-1 + ka_n-2 for n>1

for any choice of c₂. This is done by direct substitution and simplification as follows:

c₂nrⁿ = h(c₂[n-1]r^n-1) + k(c₂[n-2]r^n-2)
c₂nrⁿ = hc₂nr^n-1 - hc₂r^n-1 + kc₂nr^n-2 - 2kc₂r^n-2
c₂nr^n-2[r²-hr-k] + c₂r^n-2[hr-2k] = 0

Note that the first expression in square brackets in the preceding equation is 0 because r is a root of the characteristic equation. The second expression in square brackets is also 0 because if r is a double root of the quadratic equation x²-hx-k=0 then r=h/2 and h²+4k=0. Thus, a_n=c₂nrⁿ is a solution of the recurrence relation.

The following example explores the solution of homogeneous, linear DDS's of order 2 for the case in which the characteristic equation has complex roots.

Example 4.3: Find the first 7 values determined by the discrete dynamical system

(I) a₀ = 1, a₁ = 2
(R) a_n = a_n-1 - a_n-2

Then solve the characteristic equation and explore the construction of the solution of this system.

Solution: The first 7 terms of the sequence are easy to compute by hand:

a₀ = 1
a₁ = 2
a₂ = a₁ - a₀ = 1
a₃ = a₂ - a₁ = -1
a₄ = a₃ - a₂ = -2
a₅ = a₄ - a₃ = -1
a₆ = a₅ - a₄ = 1

The characteristic equation for (R) is:

x²-x+1 = 0

This equation has complex conjugate roots:

r = 1/2 + 31/2i/2

s = 1/2 - 31/2i/2

Earlier in this section, we acutally showed that if r and s are distinct roots of the characteristic equation, then the general solution of the system can be written as
a(n) = c₁rⁿ + c₂sⁿ for all n

Thus, in this case, the general solution is

a(n) = c₁(1/2 + 3^1/2i/2)ⁿ + c₂(1/2 - 3^1/2i/2)ⁿ for all n

(The earlier discussion was for distinct real roots r and s, but the algebra is the same for complex r and s!) Now impose the initial conditions a₀=1 and a₁=2 to obtain the equations

1 = a₀ = c₁ + c₂
2 = a₁ = c₁(1/2 + 3^1/2i/2) + c₂(1/2 - 3^1/2i/2)

These equations can be solved for c₁ and c₂ to obtain

c1 = 1/2 - 31/2i/2

c2 = 1/2 + 31/2i/2

so the solution of the given system is

a(n) = (1/2-3^1/2i/2)(1/2+3^1/2i/2)ⁿ + (1/2+3^1/2i/2)(1/2-3^1/2i/2)ⁿ

Let's check the first few values:

a₀ = (1/2-3^1/2i/2) + (1/2+3^1/2i/2) = 1
a₁ = (1/2-3^1/2i/2)(1/2+3^1/2i/2) + (1/2+3^1/2i/2)(1/2-3^1/2i/2)
a₁ = (1/4+3/4) + (1/4+3/4) = 2
a₂ = (1/2-3^1/2i/2)(1/2+3^1/2i/2)² + (1/2+3^1/2i/2)(1/2-3^1/2i/2)²
a₂ = (1/2-3^1/2i/2)(-1/2+3^1/2i/2) + (1/2+3^1/2i/2)(-1/2-3^1/2i/2)
a₂ = (-1/4+3/4) + (-1/4+3/4) = 1, etc.

It's working!

Summary:

If the characteristic equation
x²-hx-k = 0

of a homogeneous linear DDS

(I) a₀ = c, a₁ = d
(R) a_n = ha_n-1 + ka_n-2 for n>1

has complex conjugate roots

r = a ± ib

then the general solution of (R) is

a(n) = c₁(a + ib)ⁿ + c₂(a - ib)ⁿ for all n

where c₁ and c₂ are constants whose values are detmerined by the initial conditions (I).

There is a more convenient and descriptive way to write the general solution for the case in which the charactertistic equation has complex conjugate roots r = a ± ib. First, write a + ib in polar (or trigonometric) form:

a + ib = r[cos(a) + (i)sin(q)]

where r = (a²+b²)^1/2, q = Arctan (b/a)



Then, as we have seen above, the sequence of complex numbers defined by:

z_n = (a + ib)ⁿ = rⁿ(cos(nq) + (i)sin(nq))

is a solution of (R). Also, because the coefficients in the recurrence relation (R) are real numbers, the sequences of real and imaginary parts of z_n:

Re(zn) = rncos(nq)

Im(zn) = rnsin(nq)

are also solutions of (R). This means that we can also write the general solution of (R) in the form

a(n) = rⁿ(d₁cos(nq) + d₂sin(nq))

where d₁ and d₂ are real constants that are determined by the initial conditions (I). This form of the general solution is often called the real general solution of (R).

In Example 4.2, we found that the characteristic equation had complex conjugate roots:

1/2 ± 3^1/2i/2 = cos(p/3) + (i)sin (p/3)

Therefore, the real general solution of that system is

a(n) = [d₁cos(np/3) + d₂sin(np/3)] for all n

To compute the values of d₁ and d₂ that are determined by the initial values, note that

1 = a(0) = (1)d₁ + (0)d₂
2 = a(1) = cos(p/3)d₁ + sin(p/3)d₂
2 = a(1) = (1/2)d₁ + (3^1/2/2)d₂

These equations have the solutions

d1 = 1

d2 = 31/2

so the real solution of the system in Example 4.2 is

a(n) = cos(np/3) + 3^1/2sin(np/3)] for all n

The following example shows that the Method of Undetermined Coefficients can be used for non-homogeneous linear discrete dynamical systems of order 2 in essentially the same way as in Lesson 3 for systems of order 1.

Example 4.4:

Solve the following non-homogeneous linear DDS of order 2:
(I) a₀ = -7, a₁ = 38
(R) a_n = 5a_n-1 - 6a_n-2 + 2*5ⁿ

Solution:

The homogeneous recurrence relation corresponding to (R) is
(R^*) a_n = 5a_n-1 - 6a_n-2

The characteristic equation of (R^*):

x² - 5x + 6 = 0

has roots x=2 and x=3. Consequently the general solution of (R^*) is

a_n = c₁2ⁿ + c₂3ⁿ for all n

Based on the Method of Undetermined Coefficients for DDS's of order 1, we now seek a solution of the non-homogeneous recurrence relation (R) of the form

a_n = c(5ⁿ) for all n

where c is an appropriate constant determined by substitution into (R) as follows:

c(5ⁿ) = 5c(5^n-1) - 6c(5^n-2) + 2(5ⁿ)

(c-2)(5ⁿ) - 5c(5^n-1) + 6c(5^n-2) = 0

[25(c-2) - 25c + 6c](5^n-2) = 0

-50+6c = 0

c = 50/6 = 25/3

Therefore

a_n = (25/3)5ⁿ for all n

is a particular solution of (R) and so the general solution of (R) is

a_n = c₁2ⁿ + c₂3ⁿ + (25/3)5ⁿ for all n

where c₁ and c₂ are constants detmerined by the initial conditions (I).

Now impose the initial conditions (I) to obtain the equations

-7 = a(0) = c₁ + c₂ + 25/3
38 = a(1) = 2c₁ + 3c₂ + 125/3

This pair of equations has the solution c₁=-127/3 and c₂=27, so the solution of the given DDS is:

a(n) = (-127/3)2ⁿ + (27)3ⁿ + (25/3)5ⁿ

Important Point: The following Just Do It! questions are Assignment 4 for this module. There is an Assignment 4 shell file in the download folder for this module that contains the statements of these questions. Open that shell now and complete Assignment 4 according to the instructions in that document.

Just Do It!

Problem 4.1
Find the solution of the following recurrence relation of order 2:
(R) a_n = -a_n-1 + 6a_n-2

for each of the following sets of initial conditions

1. (I) a₀=1, a₁=2
2. (I) a₀=1, a₁=-3
3. (I) a₀=1, a₁=1

In each case, include a screenshot of a table of the first 6 values in the space below the solution formula.

Problem 4.2

Find the real solution of the discrete dynamical system
(I) a₀=1, a₁=2
(R) a_n = 2a_n-1 + 2a_n-2

Verify that the first 6 values computed from your solution formula agree with the first 6 values computed from the discrete dynamical system. (You can do this by including screenshots from your calculator or you can do it by hand).

Problem 4.3

Find the general solution of the recurrence relation:
(R) a_n = -a_n-1 - (1/4)a_n-2

Then find the solution that corresponds to the initial values

(I) a₀=1, a₁=1

Problem 4.4
Morse code messages are composed of two types of signals, a dot and a dash. Suppose that it takes 1 time unit to transmit a dot and 2 time units to transmit a dash.

Problem: Compute the total number S_n of different Morse code messages (message=any string of dots and dashes) that can be sent in n time units? To solve this problem, complete the following steps:

1. Show that S₁=1, S₂=2, S₃=3, S₄=5 by just listing all of the possible messages in each case.

2. Explain why the following recurrence relation holds for S_n:
   S_n = S_n-1 + S_n-2 for n>2

3. Find a formula for S_n as a function of n; that is, solve the discrete dynamical system:
   (I) S₁ = 1, S₂ = 2
   (R) S_n = S_n-1 + S_n-2 for n>2

Problem 4.5

1. Find the general solution of the recurrence relation:
   (R) a_n = 7a_n-1 - 10a_n-2 for n>1

2. Find the solution of the DDS consisting of the recurrence relation (R) and the initial conditions
   (I) a₀=2, a₁=7

3. Create with your calculator and paste in below a table of values for n=0,1,2,3,4,5,6 for the "ratio sequence"
   u_n = a_n / a_n-1 for n>0

   for the solution to (b). Then do the same for two other sets of initial conditions of your choice. Are there any conjectures that you can make about the values of this ratio sequence?

4. Can you explain what you observed in (c) on the basis of the general solution computed in (a)?