Objectives of This Lesson:

• To identify discrete dynamical systems that are linear, homogeneous, or affine.
• To describe solutions for affine and homogeneous systems of order 1.
• To identify and compute equilibrium values of discrete dynamical systems.
• To construct and interpret cobweb graphs for discrete dynamical systems.

The solution of linear equations ax+b=c is one of the early and important topics in a beginning algebra course. That is because linear equations are relatively simple to analyze and solve, and because such equations arise frequently in applications of mathematics. The same is true of linear discrete dynamical systems. But what exactly is a linear discrete dynamical system?

2.1: Definitions

Suppose a_n = f(a_n-1, a_n-2, ..., a_n-p, n) for n > k+p-1 is the recurrence relation for a discrete dynamical system of order p:
a_k, a_k+1, ..., a_k+j, ...

The recurrence relation f is linear if there are p constants c₁, c₂, ..., c_p and a function g(n) such that f can be written as:

a_n = c₁a_n-1 + c₂a_n-2 + ... + c_pa_n-p + g(n)
1. If g(n) is the zero function, the linear recurrence relation is called homogeneous; otherwise, it is non-homogeneous.
2. If g(n) is a non-zero constant function of n (i.e., for some non-zero constant M, g(n)=M for all n), then the linear (non-homogeneous) recurrence relation is affine.

Examples 2.2

1. The recurrence relations of order 1 for the Chemical Spill Problem (a_n = .7a_n-1 + 12) and for the Car Loan Problem (a_n = 1.05a_n-1 - 6000) are linear; in fact, they are affine.
2. The recurrence relations of order 1 for the Population Puzzle (p_n = (1+r)p_n-1 - (r/c)p_n-1²) is not linear.
3. The recurrence relation for the Fibonacci sequence,
   (I) a₀=1, a₁=1
   (R) a_n = a_n-1 + a_n-2 for n>1
   is linear, homogeneous, and of order 2.

The simplest discrete dynamical systems to solve are the discrete dynamical systems that are either homogeneous and of order 1:

(I) u₀=c
(R) u_n=ru_n-1 for n>0

or are affine and of order 1:
(I) u₀=c
(R) v_n=rv_n-1+d for n>0

where d is non-zero and r is not equal to 1.

The distinctions between these two types of systems come through the absence or presence of a constant term in the recurrence relation defining the system.

To find the solution of the general homogeneous discrete dynamical system of order 1:

(I) u₀ = c
(R) u_n = ru_n-1 for n>0,

just iterate the recurrence relation (R) and substitute the initial value:

u₁ = ru₀ = cr
u₂ = ru₁ = cr²
u₃ = ru₂ = cr³
u₄ = ru₃ = cr⁴

It appears from these calculations that the solution of the given system is:

u(n) = u_n = crⁿ for all n

Just as in Example 1.5, you can prove that this is the one and only solution of the given system. To prove this, you need to use mathematical induction. You will be asked to do that in the next Just Do It! problem list.

One can show that the solution to the affine, non-homogeneous discrete dynamical system:

(I) v₀ = c
(R) v_n = rv_n-1+d for n>0

is given by v(n) = v_n = rⁿ(c - d/(1-r)) + d/(1-r) provided that r is not equal to 1.

In a Just Do It! exercise, you will have the opportunity to show that this function provides a general solution to the given affine dynamical system.

The functions u_n and v_n are actually general solutions for the respective dynamical systems because we have not specified the initial value c of the systems.

Let's summarize these important results:

1. The general solution of the homogeneous recurrence relation of order 1:
   u_n = ru_n-1 for n>0

   is:

   u_n = crⁿ for all n

   This solution has u₀=c as its initial value.

2. The general solution of the affine non-homogeneous recurrence relation:
   v_n = rv_n-1+d for n>0,

   where d is non-zero and r is not equal to 1 is:

   v_n = rⁿ(c - d/(1-r)) + d/(1-r) for all n

   This solution has v₀=c as its initial value.

While the general solution given in (1) is easily guessed by iteration, the general solution given in (2) is not so easy to guess. We will discuss a method for identifying the correct form of the general solution of non-homogeneous linear recurrence relations in Lesson 3.

Use the preceding result to find the solution to the system that models the Chemical Spill Problem discussed in the introduction:
(I) a₀=0
(R) a_n = .7a_n-1 + 12 for n>0

Solution:

This is an affine system with initial value a₀=0, r=.7, d=12, so the preceding result states that the solution is

a_n=(.7)ⁿ(0 - 12/(1-.7)) + 12/(1-.7) = -40(.7)ⁿ+40 for all n

This agrees with the solution discussed in Example 1.5. Note that for large values of n, the formula for the solution shows that the value of a_n is near 40 because (.7)ⁿ approaches 0.

In the previous example, we noted that the values of the discrete dynamical system approach the value 40 when we started with an initial value of 0 for the system. That is, the difference between the value 40 and the value of a_n can be made as small as one wishes if n is large enough. A value such as this is known as an equilibrium value for the system.

The study of equilibrium values and limits associated with discrete dynamical systems is key to understanding the nature and behavior of such systems. An equilibrium value has the property that if it is used as the initial value, then all success ive values associated with the system are equal to the equilibrium value. In fact, that is the basis for the definition of the equilibrium value.

2.4: Definition

The number a is called an equilibrium value or fixed point for a discrete dynamical system if u_k = a for all values of k when the initial value u₀ is set at a . That is, u_k = a is a constant solution to the recurrence relation for the dynamical system.

Another way of characterizing such values is to note that a number a is an equilibrium value for a dynamical system u_n = f(u_n-1, ..., u_n-p, n) if and only if a satisfies the equation a = f(a, a, ..., a).

Using this definition, we can show that a linear homogeneous dynamical system of order 1 only has the value 0 as an equilibrium value.

The first-order affine system

(I) v₀=c
(R) v_n=rv_n-1+d for n>0

has an equilibrium value of d/(1-r) provided r is not equal to 1. This is found by noting that e = re + d, where e is the equilibrium value for the system, should it exist.

In general, dynamical systems may have no equilibrium values, a single equilibrium value, or multiple equilibrium values. Linear systems have unique equilibrium values. The more non-linear a dynamical system is, the more equilibrium values it may have.

One can observe the longer term behavior of discrete dynamical systems under different initial values through the use of cobweb graphs. Cobweb graphs provide a nice visual way of tracking the generation of the successive values of the discrete dynamical system from the initial value onward.

Example 2.4:

Construct the cobweb graph of the affine system defined by:

(I) u₀=0
(R) u_n=.75u_n-1 + 16 for n>0

Solution:

The cobweb graph for this system is shown below.



But how was this graph constructed? Consider mapping of the initial value u₀ = 0 by the function y = 0.75x + 16. This is exactly what the dynamical system does to the input value. It multiplies it by 0.75 and then adds 16 to it, arriving at the output value of 0.75(0) + 16 or 16. Think now of drawing a line from the point (0, 0) to the point (0, 16) to illustrate this sending of "0 up to 16."

The graph shows the line segments from (0, 0) up to (0, 16). Then we see a horizontal line from (0, 16) across to the line y = x to the point (16, 16). This translates the output from the first iteration 16 into a position of x = 16 for the next input. The second vertical line takes this x = 16 and evaluates the equation y = 0.75x + 16 using x = 16 as an input. The intersection of the vertical line through (16, 16) intersects the line y = 0.75x + 16 at the point (16, 28). Here again, we see a horizontal line moving the action off to the right to the point (28, 28). This translates the output from the second iteration into input for the next iteration with the vertical line through (28, 28) taking the value of x = 28 to the value of 37 at the point (28, 37). Again, the translation across to the line y = x gives us a setup for the next iteration, and so on. Eventually we see the process moving toward the equilibrium value of 64 which is represented here by the point (64, 64).

The following cobweb graph, constructed in the same manner as the preceding example for the affine system

(I) u₀=2
(R) u_n=(-.8)u_n-1+2

illustrates why these are called cobweb graphs.



Here one can easily see the "cobweb nature of the graph and see the values "curving" back toward the equilibrium value of 1.1111....

Cobweb graphs can be developed on the TI-82 with a few keystrokes. First, press Y= to enter the recurrence relation representing a discrete dynamical system:

u_n = 0.75u_n-1 + 16 for n > 0 and u₀ = 0.

Enter the WINDOW editor by pressing on the WINDOW key beneath the screen.

Set

U_nStart=0
nStart=0
nMin=0
nMax=10
Xmin=0
Xmax=75
Xscl=10
Ymin=0
Ymax=75
Yscl=10


These choices are reasonable given our previous exploration of this DDS.

Then use the arrow key in the WINDOW editor to toggle to FORMAT and then to Web in the second row as in the figure below.



To examine the actual values of the system through this cobweb analysis, touch TRACE and then observe successive values of the dynamical system through successive strokes of the right-arrow cursor button. The frames below show the analysis of the above system for the first six iterations of the tracing process outlined.







If you continue hitting the right arrow key, you will see that both the x and y values are approaching 64. In fact, because the equation
e=.75e+16

has the solution e=64, 64 is the exact equilibrium value for this system.

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

Just Do It!

Problem 2.1
For each of the following discrete dynamical systems:
1. (I) u₀=0
   (R) u_n=.5u_n-1-1 for n>0

2. (I) u₀=1
   (R) u_n=1.5u_n-1+2 for n>0

3. (I) u₀=-2
   (R) u_n=-.3u_n-1 for n>0

do the following with your calculator:
1. Create a table of the first 6 values.
2. Create a cobweb graph for the system that discplays the first ten iterates nicely.

Paste screen shots of the tabls and cobweb graphs in the space below each of the systems in the Assignment 2 shell.

Problem 2.2

Find solutions and equilbrium values, if there are any, for the discrete dynamical systems in Problem 2.1.

Problem 2.3

For the following affine discrete dynamical systems:

1. u_n=u_n-1-2 where u₀=4
   
2. u_n=u_n-1+3 where u₀=1

the value of r is 1, so the solution formulas given in this lesson do not apply.
1. Use iteration (by hand or with your calculator) to explore the first few terms of each sequence.

2. On the basis of (i), conjecture a formula for a solution u(n) of the general affine system with r=1:
   (I) u₀=c
   (R) u_n=u_n-1+d for n>0

3. Prove or disprove your conjecture in (ii).

Problem 2.4

A debt of $10,000 is to be amortized by equal payments of $400 at the end of each month, plus a final payment after the last $400 payment is made. If the interest is at the rate of 1% compounded monthly (the same as an annual rate of 12% compounded monthly),

1. Write a discrete dynamical system that models the situation.
2. Construct a table showing the amortization schedule for the required payments.
3. Find a solution for the system.

Problem 2.5

Use mathematical induction to prove that u(n) is a solution of the homogeneous system

(I) u₀=c
(R) u_n = ru_n-1 for n>0

then u(n) can be written in the form

u(n) = crⁿ for all n