Introduction to DDS's

• To acquaint you with discrete dynamical systems in three contexts with representations that make use of tables, graphs, and recursive relations.

• To intuitively introduce you to the terminology of discrete dynamical systems.

  A discrete dynamical system (DDS) is a system in which a quantity changes value over discrete time intervals, and the values for a given time interval can be computed from the values in previous intervals. The contexts in which discrete dynamical systems occur ranges from financial settings, such as savings account and loan balances, to the study of ecological and environmental data.

  The mathematics involved in and developed through the study of discrete dynamical systems serves as an important bridge from secondary school algebra to the study of calculus, linear algebra, differential equations, discrete mathematics, and statistics. Perhaps even more important, the study of this subject coalesces many of a student's understandings of the concept of function and, at the same time, develops important problem solving skills. Consequently, teachers can use content on discrete dynamical systems to enrich algebra, precalculus, and calculus courses, and to help their students appreciate the relationship between these subjects.

A Chemical Spill Problem

Problem: An industrial spill of hazardous materials has occurred and your plant safety team has entered the building to begin the cleanup of the toxic substance. The team members are wearing protective suits to prevent the possible fatal side–effects of prolonged exposure to the substance. The suits are constructed of a material that chemically neutralizes toxic substance. However, over time, the chemical coating in the garment's fibers breaks down and loses its ability to protect the wearer from exposure to the hazardous materials.

Experience shows that the cloth can neutralize 30 percent of the chemical which it encounters per hour. Experience also shows that, during periods of exposure, the garment encounters 12 micrograms of the chemical per hour. Standards for human exposure to the toxic substance indicates that such suits are safe for use until they reach a level of 35 micrograms of the toxic chemical in their fibers.

Question: Under these conditions, how many hours can the safety team work without having to worry about changing their outfits?

This problem is easily modeled through the use of a discrete dynamical system. If we think of the time intervals, in hours, as the variable n and the amount of chemical in the suit at the end of an interval of length n hours as a_n, we can model the chemical residue in the suits by the relationship:

a_n = 0.7 a_n-1 + 12 for n > 0 and a₀ = 0.

Here the 0.7 coefficient describes the amount of residue that remains in the suit after each period of one hour, –the treated garment cloth has neutralized the other 30 percent. The term 12 that is added reflects the new contamination. As this process starts from a clean suit, the initial value, a₀ is 0.

The following table shows the value of the residual contaminant a_t in the suit after t hours:

n 0 1 2 3 4 5 6 7 8 9 an  0.00  12.00 20.40 26.28 30.40 33.28 35.29 36.71 37.69 38.39

n 10 11 12 13 14 15 16 17 18 19 an 38.87 39.21 39.45 39.61 39.73 39.81 39.87 39.91 39.93 39.95

n 20 21 22 23 24 25 26 27 28 29 an 39.97 39.98 39.98 39.99 39.99 39.99 40.00 40.00 40.00 40.00

The entries in this table can be calculated successively by using the formula given above.
For example, because a₀=0, it follows that
a₁ = .7a₀+12 = .7(0)+12 = 12,
a₂ = .7(12)+12 = 20.40, and so on.

It does not take a great deal of study to note that the wearer of the suit should be considering a change of suits after 6 hours for sure, but probably after 5 if the wearer understands experimental measurement errors! Note that as time increases, the value of accumulation of the chemical in the cloth seems to level off at 40 micrograms. What causes this to happen? Could we have predicted this?

A Population Puzzle

Surveys of the owl population in a certain region indicate that the population of owls both grows and declines through factors related to the births and deaths in the population. If the population of owls at the beginning of the n^th year might be represented by p_n, the number of births in year n is proportional to p_n; that is births equals bp_n. In a similar manner, the number of deaths can be represented as dp_n. Hence the population in p_n might be represented as p_n = p_n–1 + bp_n–1 – dp_n–1. This can alternatively be written as
p_n – p_n–1 = (b – d)p _n–1

or p_n = (1+ r) p_n–1 where r = b – d.

However, the value of r itself varies as a function of the size of the population. When the population grows, the amount of available food decreases. As a result, the value of r decreases. In a similar, but different fashion, when the size of the population decreases, the resources will support a higher reproduction rate. Hence the value of r increases.

It is reasonable to suppose that there is an optimal population C for keeping r constant. C is sometimes referred to as the carrying constant for the region and species. It is the population size that produces a constant value for r. When the size of the population exceeds C, the value of r decreases. When the population size is less than C, the value of r increases.

Consider the expression r[1–(p_n–1/C)] as a model for the change in population from one year to the next. When C equals p_n–1, the expression has a value of 0 and the change in population size is 0. When C is greater than p_n–1, the effect is to have a multiplier that is less than 1. When C is less than p_n–1, the effect is to have a multiplier that is greater than 1. Thus the expression r[1–(p_n–1/C)]. p_n–1 is a good model for the change in population from one year to the next. In fact, one could write


p_n – p_n–l = r[1–(p_n–1/C)] p_n–1

This can be written as

p_n = (1+r)p_n–1 – p_n–1²(r/C)

This equation is called the logistic equation, and – p _n–1²(r/C) is called the damping term for the population.

Suppose that a restricted area with a carrying capacity of 300 owls has an initial poulation of 200 owls. The following table shows the values that obtain over a 15 year period for r equal to 0.4. 0.6 and 0.8.

n	pn (r = 0.4)	pn (r = 0.6)	pn (r = 0.8)
0	200	200	200
1	227	240	253
2	249	269	285
3	266	286	296
4	278	294	299
5	286	297	300
6	291	299	300
7	295	300	300
8	297	300	300
9	298	300	300
10	299	300	300
11	299	300	300
12	300	300	300
13	300	300	300
14	300	300	300
15	300	300	300

 

Here one can clearly see the role played by the various variables as time continues. The larger r is in value, the quicker the population moves to a stabilized size and growth discontinues.

The Car Loan Problem

Suppose that you purchased a $25,000 car and made a down payment of $5000. This left you with a balance of $20,000 which you needed to finance with a loan from your local bank. You agree upon a financial arrangement which requires you to make an annual payment of $6000 on the anniversary of the loan. Given your background in mathematics, you wish to examine some of the parameters involved with the terms of the loan. Suppose that the bank is currently charging 5% interest compounded yearly on the outstanding balance of the loan. What is the effect of making annual payments of $6000? How long will it take to pay off the loan under these conditions?

Letting a_n represent the amount of money outstanding at the end of the nth year, we can represent the loan situation as follows:

a_n = 1.05a_n–1 - 6000 for n>0 and a₀ = 20,000.

That is, the loan balance in the nth year is equal to the loan balance in the previous year upward adjusted by the interest due and downward adjusted by the annual payment. However, this sequence of steps is only good if there is a place to start the calculation. This is the initial value of the loan––$20,000. Iterating, or stepping through this relationship from one year to another, we find the balance schedule at right. Thus, the car wil be paid off in four payments with the final payment of $4,237.50.

n an 0 20,000.00 1 15,000.00 2 9,750.00 3 4,237.50

However, if you thought that the payment of $6000 per year was too steep, you might wish to examine what an annual payment of $500 would do.

 

n	0	1	2	3	4	5
an	20000.00	20500.00	21025.00	21576.25	22155.06	22762.82

This clearly shows that the long term pattern associated with this payment schedule is clearly to the bank's liking, but not to yours. This information causes us to reflect a bit deeper on the situation at hand and notice that a yearly payment of $1000 would just meet the interest costs and keep us in a long term stage of equilibrium with our initial loan value of $20,000. This is shown by the table below which describes this stable situation.

n	0	1	2	3	4	5
an	20000.00	20000.00	20000.00	20000.00	20000.00	20000.00

 

The preceding three examples illustrate the focus of our work in this course. When do discrete dynamical systems move to stable patterns, when do they drift aimlessly through a myriad of values in chaotic behavior, when do they flip between a predictable set of values? How can we use the our knowledge of mathematics to understand, predict, and control what happens in each of these settings?

 

Lesson 1: Basic Concepts and Examples

Objectives of This Lesson:

• To represent a discrete dynamical system in terms of tables, diagrams, and equations.

• To recognize general solutions of recurrence relations (difference equations) and solutions of discrete dyncamical systems and represent them symbolically.

• To recognize the order of a discrete dynamical system.

A discrete dynamical system is a special way of defining or prescribing a sequence of numbers. More precisely:

1.1 Basic Definitions:

A discrete dynamical system (DDS) is a sequence a_k, a_k+1, a_k+2, ..., a_k+j, ... that is defined as follows:
For some positive integer p,
(I) the first p terms of the sequence a_k, a_k+1, ..., a_k+p-1 are given explicitly.
(R) for all n > k+p-1, a_n is a given function of the preceding p terms:
a_n = f(a_n-1, a_n-2, ..., a_n-p, n)

Given a discrete dynamical system a_k, a_k+1, a_k+2, ..., a_k+j, ..., the function f in (R) is called the recurrence relation or the difference equation. The first p terms a_k, a_k+1, ..., a_k+p-1 given in (I) are called the initial values, and the smallest value of p for which (I) and (R) hold is the order of the system.

Example 1.2:

1. All of the discrete dynamical systems considered in the Introduction are of order 1:
   1. Chemical Spill Problem
      (I) a₀=0
      (R) a_n = 0.7a_n-1 + 12 for n>0

   2. The Population Puzzle
      (I) p₀=300
      (R) p_n = (1+r)p_n-1 - p_n-1²(r/c) for n>0

   3. The Car Loan
      (I) a₀=20,000
      (R) a_n = 1.05a_n-1 - 6000 for n>0

2. The famous Fibonacci sequence, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... defined by
   (I) a₀ = 1 ; a₁ = 1
   (R) a_n = a_n-1 + a_n-2 for n > 1
   is a discrete dynamical system of order 2.

3. A system defined by the recurrence relation R_n = 3R_n-2 + 2 for n > 1 and an initial value for R₀ of 5 and R₁ = 8 has order 2 as the maximum reach back to define a new term’s value is two steps, i.e. from n to n-2.

4. A system defined by the recurrence relation f_n = f_n-3 + f_n-7, where n > 6 and known values for f_n for n = 0 to 6 has order 7 because one has to reach back 7 levels to find the value of the second term on the right hand side of the recurrence relation.

Example 1.3:

Given a discrete dynamical system, one can use its initial value(s) and its recurrence relation to compute as many terms of the sequence defined by the system as desired. This process is called iteration. The following example illustrates iteration for a very simple discrete dynamical system of order 1.
(I) a₀ = 10
(R) a_n = 2a_n-1 for n > 0

Solution:

a₀ = 10

a₁ = 2a₀ = 2*10 = 20

a₂ = 2a₁ = 2*20 = 40

a₃ = 2a₂ = 2*40 = 80

It is easy to guess from the calculation of a₀, a₁, a₂, a₃ by iteration that the pattern for the values of all a_n is:
(*) a_n = 10 * 2ⁿ for all n.

Note that the preceding formula gives a_n as an explicit function a(n) that does not depend on preceding terms of the sequence like the recurrence relation (R) does. It is also easy to see from the iteration in Example 1.3 that if the initial value a₀=10 had been left unspecified, then the explicit formula for a_n would still be easy to guess as

(**) a_n = a₀ * 2ⁿ for all n

The formula (*) is the "solution" of the discrete dynamical system defined by:

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

while the formula (**) is the "general solution" of the recurrence relation (R). More precisely and generally, we define these terms as follows:

1.4: Definitions

Suppose that a_k, a_k+1, ..., a_k+j, ... is a discrete dynamical system of order p defined by:
(I) Given initial values for a_k, a_k+1, ..., a_k+p-1
(R) A recurrence relation a_n = f(a_n-1, a_n-2, ..., a_n-p, n)

A function a(n) of n that gives the initial values (I) and also satisfies the recurrence relation (R) is a solution of this discrete dynamical system.

A function a(n) of n containing p parameters c₁, c₂, ..., c_p that satisfies the recurrence relation (R) is a general solution of this discrete dynamical system.

Thus, a discrete dynamical system and a solution of that system are just two different ways of prescribing an infinite sequence of numbers a_k, a_k+1, ..., a_k+j, ... . The discrete dynamical system prescribes this sequence in terms of initial values and a recurrence relation, while the solution gives an explicit function a(n) that you can use to compute any desired term of the sequence without first computing its predecessors.

Example 1.5

Show that a(n) = a_n = -40(.7)ⁿ + 40 for all n is a solution for the chemical spill dynamical system:
(I) a₀ = 0
(R) a_n = .7a_n-1 + 12 for n>0

Solution:

Method 1: Tables of values

Enter the following sequences into your calculator:

u_n = -40(.7)ⁿ + 40
v_n = .7v_n-1 + 12
v₀ = 0
and then use the Table facility on your calculator to check that the values of u_n and v_n are the same. For example, here is how the TI-82 calculator displays the tabular values for the first few iterations of the system.

If you scroll down the table further on your calculator, you will see that un and vn continue to agree. This is strong evidence that vn is a solution of the chemical spill problem.

Method 2: Algebraic proof.

You can prove that
(*) a(n) = a_n = -40(.7)ⁿ + 40 for all n

is a solution of the discrete dynamical system:
(I) a₀ = 0
(R) a_n = .7a_n-1 + 12 for n > 0

by simply checking algebraically that (*) satisfies (I) and (R):

a₀ = -40(.7)⁰+40 = -40+40 = 0 : OK
.7a_n-1+12 = (.7)[-40(.7)^n-1+40]+12 = -40(.7)ⁿ+28+12 = -40(.7)ⁿ+40 = a_n : OK

This proves that (*) is a solution of the dynamical system.

Is it possible that there are other (different) solutions? The answer is no. By using mathematical induction, you can prove that the sequence defined by (I) and (R) can always be written in the form (*). In fact, the preceding calculations are essentially the same as those you would use in an induction proof.

Important Point: In many real-world applications, it is relatively easy to write down a discrete dynamical system that models the application, and relatively difficult to write down a solution for that system. For many important discrete dynamical systems, some solution method must be applied to obtain an explicit solution. Once an explicit solution is obtained, it can be used to provide new information about the real world application that was modeled by the discrete dynamical system. Depending on how well this new information agrees with known data for the real-world application, one can accept or refine the discrete dynamical system model, or reject the model as unrealistic and try to find a different model.

This process is depicted in the flow diagram below:

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

Just Do It!

Problem 1.1
Which of the following are discrete dynamical systems? Explain briefly why or why not in each case. State the order of the discrete dynamical systems in the list.
1. a_n = a_n-2 + 3n + 6 for n>1 where a₀=2 and a₁=3.
2. a_n = 2a_n + 3 for n>0 where a₀=5.
3. a_n = 3n + 6 for n>0 where a₀=2.
4. a_n = a_n-1² + 2a_n-2 + 3n + 6 for n>1 where a₀=2 and a₁=3.

Problem 1.2

Use mathematical induction to prove that any solution of the Chemical Spill Problem can be expressed in the form: a_n = (-40)(.7)ⁿ + 40 for all n

Problem 1.3
1. Use your calculator to create a table that gives strong evidence that
   (*) a(n) = a_n = 5(.5)ⁿ + 2n - 2
   is a solution of the discrete dynamical system:
   (I) a₀=3
   (R) a_n = .5a_n-1 + n
2. Prove that (*) is a solution of this DDS algebraically.

Problem 1.4

Use your calculator to generate a table of the Fibonacci sequence. Insert a screen shot of the table section in your answer that include the value a₂₅. (If necessary, review the TI-Graph Link Tutorial and/or the Sequences with the TI-82(85) Tutorial to solve this problem).

Problem 1.5

Wildlife experts have determined that there are 1250 Dart birds in the entire United States. A bird is placed on the endangered species list when the populations falls below 100 birds. Experts have also determined that 7% of the Dart bird population either dies or are killed by poachers each year. They have, however, been able to successfully hatch Dart bird chicks in captivity. This program adds 5 Dart birds per year. Assuming that the stated conditions persist:
1. Write a discrete dynamical system of order 1 that models the population p_n of Darts in the U.S. n years from now.

2. Use the Table and Graph features of your calculator to determine if the Dart bird will be declared an endangered species. (Paste in screen shots from your calculator to support your answer).

Problem 1.6

The function a(n) = (-100,000)(1.05)ⁿ + 120,000 is a solution of the DDS given by the Car Loan Problem in the Introduction:
(I) a₀=20,000
(R) a_n=1.05a_n-1-6000 for n>0
1. Provide strong evidence that a(n) is a solution with a screen shot from your calculator.

2. Prove that a(n) is a solution by algebraic methods.

Lesson 2: Linear Discrete Dynamical Systems

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:

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.

 

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.

 

Example 2.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.

 

Equilibrium Values of Discrete Dynamical Systems

 

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.

 

Cobweb Graphs for Discrete Dynamical Systems

 

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

    

• 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

Lesson 3: Constructing Solutions To Linear Discrete Dynamical Systems

Lesson 3:

Objectives of This Section:

• To develop methods of finding solutions to linear discrete dynamical systems using iteration and the method of undetermined coefficients.

• To examine the stability nature of equilibrium points when they do exist.

 

Introduction

As we have already pointed out in Lesson 1, finding a solution to a discrete dynamical system of order p

(I) a_k, a_k+1, ..., a_k+p-1 are specified
(R) a_n=f(a_n-1, ..., a_n-p, n)

is important to the study of such systems, because a solution a(n) allows one to move immediately to the value of a_n knowing only the value of n. To find the value of a_n using the discrete dynamical system, one would have to work up from the initial value(s) (I) to get the value of a_n by using the recurrence relation (R). In this lesson, we will examine an important method for constructing such solutions for linear discrete dynamical systems. Although the method will only be used for systems of order 1 in this lesson, it applies to higher orders as well.

Recall that there are two forms of solutions. The first is a general solution. This is a function a(n) that satisfies the defining recurrence relation for the system and which contains p constants c₁,c₂, ..., c_p where p is the order of the system, representing arbitrary initial values which the system may have. A particular solution, or, simply, solution, is a function a(n) which satisfies the defining recurrence relation for the system and also has a given initial values for the system. As such, it does not contain any arbitrary constants that represent unknown initial values. This solution is "particular" to specific initial values.

In Lesson 1, we proved that the one and only solution of the homogeneous system of order 1:

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

can be written in the form

(*) a(n) = a_n = c₀rⁿ for all n

We also stated, but did not prove, that the solution of the affine system of order 1

(I) a₀=c₀
(R) a_n = ra_n-1+b

is given by

a(n)=rⁿ(c₀ - (b/(1-r))) + (b/(1-r)) for all n provided r is not equal to 1.

The Method of Undetermined Coefficients with Systems

Although we checked that a_n=rⁿ(c₀-b/(1-r)) + b/(1-r) is a solution of the affine system
(I) a₀=c₀
(R) a_n = ra_n-1+b for n>0

we did not explain how we arrived at that form of the solution. The following example begins with the solution for a homogeneous system and then explores the proper solution for two different affine, non-homogeneous systems.

Example 3.1 (Part 1): Suppose the Angler’s Club knows that the number of bass in their breeding pond grows at a rate of 40% per annum. Further, they know that 300 bass were planted in the pond after the pond had been cleared of all fish by shocking. What is a good estimate of the number of fish in the pond after 10 years?

Solution: This problem asks us to find the number of bass in the breeding pond, b_n for n = 10, given the recurrence relation of b_n = 1.40b_n-1 for n> 0 and b₀ = 300. We could iterate through the values of b_i for I = 1, 2, 3,...,10 to get the value of approximately 8678 fish, depending on how we chose to handle rounding the decimal portions of a fish at a given state.

A solution to this homogeneous dynamical system using the formula of Lesson 2 would be b_n = (300)(1.4)ⁿ. Evaluating it for n = 10, it gives approximately 8678. However, the use of the solution allowed a direct approach to the value, whereas the iterative method required considerably more steps.

Solutions to linear discrete dynamical systems of order 1 are not always so easy to find, as in the case of homogeneous systems. Suppose instead that you are looking at a system such as b_n = 1.40b_n-1 + 50 for n > 1 and b₀ = 300.

Example 3.1 (Part 2): Let's analyze the situation in which the Angler's Club adds an extra 50 fish to the pond each year to supplement the natural growth of the population. This situation is modeled by the DDS (I) b0=300 (R) bn=1.40bn-1+50 for n>1 Looking at a graph of the bass population using the TI-82, we see that the population seems to be modeled by an exponential function with a positive y-intercept. The vertical scale is 0 to 2000, while the horizontal scale is from 0 to 10.

That is, we might expect that the solution to take the form of b_n = c₁rⁿ + c₂, where c₁ and c₂ are constants depending on the actual values of the dynamical system itself. They are our undetermined coefficients. If such a form for a function would satisfy the equation, it is the case that the values for b_n and b_n-1 would have to take on the values

b_n = 1.40ⁿ c₁+ c₂ and b_n-1 = 1.40^n-1 c₁+ c₂

where the constants c₁ and c₂ are determined by the discrete dynamical system and its initial value. Further, we know that any such solution must satisfy the original discrete dynamical system. Hence,

b_n = 1.40b_n-1 + 50 for n > 0

can be written as

(1.40ⁿ c₁+ c₂) = 1.40 (1.40^n-1 c₁ + c₂) + 50 for n > 0

Doing the algebraic manipulations, we can solve for c₂ to obtain c₂=-125, thereby getting the general solution
b_n = c₁(1.40)ⁿ – 125 for all n

To find the particular solution determined by the initial condition b₀ = 300, we now evaluate the general solution for b₀ = 300. This gives us

300 = b₀ = c₁(1.40)⁰-125 = 300.

Solving for c₁, we have c₁ = 425. This gives us our solution: b_n = 425(1.40) ⁿ – 125. Substituting this back into the original discrete dynamical system, we see that it checks and hence b_n = 425(1.40)ⁿ – 125 for all n is a solution for the discrete dynamical system b_n = 1.40b _n-1 + 50 for n > 0 and b₀ = 300. After 10 years, this model predicts a bass population of b₁₀=12,168 bass, as compared to only 8,678 without restocking.
Our solution of this problem was obtained by a procedure called the Method of Undetermined Coeffiecients. Here is a summary:

Summary of the Method of Undetermined Coefficients for Affine Discrete Dynamical Systems

Given an affine system

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

look for a solution of the form

(*) a(n) = a_n = c₁rⁿ + c₂ for all n

where c₁, c₂ are constants that are determined by substituting (*) into (I) and (R) and solving the resulting equations for c₁ and c₂.
Example 3.2 (Part 1): When a program to clean up a lake began, it was estimated that the lake contained 300 tons of chemical pollutants from farm runoffs and waste from nearby industries. Approximately 20% of the pollutant present in the lake is removed or neutralized each year by solar oxidation and by streams leading into or out of the lake. By imposing new pollution control measures, engineers estimate that they can reduce the amount of new pollutant entering the lake to 20 tons per year. Analyze the effect of this program on the pollution level in the lake.

Solution: If p_n is the number of tons of pollutant in the lake n years after the pollution control measures are initiated, then the given information is modeled by the following discrete dynamical system:

(I) p₀=300
(R) p_n = .8p_n-1+20 for n>0

This is an affine system very similar to the one solved in Example 3.1 Part 2. As in that example, we can apply the Method of Undetermined Coefficients to look for a solution of the form

(*) p(n)=c₁(.8)ⁿ + c₂

where the coefficients are determined by imposing the conditions (I) and (R):

(R) c₁(.8)ⁿ + c₂ = .8[c₁(.8)^n-1+c₂] + 20

By simplifying the preceding equation, we see that c₂=.8c₂+20; that is, c₂=100. This means that p(n)=c₁(.8)ⁿ+100 is the general solution of (R). Now impose the condition (I) to evaluate c₁:

300 = p(0) = c₁(.8)⁰+100

Thus, c₁=200 and

(**) p(n) = 200(.8)ⁿ+100

is the solution of the discrete dynamical system.

If you tabulate the function (**) on a TI-82, you can see that the new pollution control program will reduce the pollutant level by almost half in six years.

However, the solution for (**) also shows that the pollution level of the lake can never be brought below 100 tons under the new program because, although the term 200(.8)ⁿ approaches 0 as n increases, the constant term, 100, forces p(n) to exceed 100 for all n.

The Method of Undetermined Coefficients for Non-Homogeneous Systems of the Form a_n=ra_n-1+dsⁿ

Example 3.2 (Part 2): Studies indicate that any effort to restrict new pollution of the lake to less than 20 tons for the first year would result in serious economic hardships for the farms and industries around the lake. However, given some time to install new equipment and implement new operational practices, engineers estimate that it is practical to reduce the influx of new pollutant to 20 tons during the first year and by 25% each year thereafter. Analyze the effect of this modified program on the pollution level of the lake.

Solution: The modified program is modeled by the discrete dynamical system:

(I) p₀=300
(R) p_n=.8p_n-1+20(.75)^n-1 for n>0

This is a linear DDS in which the non-homogeneous term, 20(.75)^n-1, is an exponential function. Based on the method applied in Example 3.1 and Part 1 of Example 3.2, we might succeed in finding a solution of the form:

(*) p(n) = c₁(.8)ⁿ+c₂(.75)ⁿ

for appropriate choices of the coefficients c₁ and c₂. Substitute (*) into (R):

c₁(.8)ⁿ+c₂(.75)ⁿ = .8[c₁(.8)^n-1+c₂(.75)^n-1] + 20(.75)^n-1

Simplify this equation to obtain:

c₂(.75) = .8c₂+20

Therefore, c₂ = 20/(-.05) = -400, and so the proposed general solution of (R) is

p(n) = c₁(.8)ⁿ - 400(.75)ⁿ

Now impose the initial condition (I):

300 = p(0) = c₁-400

Thus c₁=700 and so the proposed solution of this modified DDS is

(**) p(n) = 700(.8)ⁿ - 400(.75)ⁿ

It is easy to check that this function satisfies both (I) and (R) so it is a solution to the modified pollution control model for the lake.

The table of values of the solution p(n) constructed on the TI-82 and displayed at right shows that this modified pollution control program will reduce lake pollution by nearly two-thirds in just six years.
Scrolling down the table further shows that in 15 years, less than 20 tons of pollutant will remain in the lake. The form of the solution p(n) also shows that if the modified program is maintained indefinitely, the lake pollution will decrease toward 0 because p(n) approaches 0 as n gets larger and larger.

The Method of Undetermined Coefficients for Non-Homogeneous Systems of the Form a_n=ra_n-1+kn+m

Example 3.2 (Part 3): Suppose that the initial pollution control program of reducing new pollution of the lake to 20 tons per year is initiated but that "backsliding" takes place as time goes on. More specifically, suppose that the influx of new pollutant is limited to 20 tons during the first year, but then increases at a rate of 5 tons per year in each succeeding year. Analyze the effect of such "backsliding" on the pollution level of the lake.

Solution: The discrete dynamical system that models this "backsliding" on the pollution control program is:

(I) p₀=300
(R) p_n=(.8)p_n-1 + 20 + 5(n-1) for n>0

The non-homogeneous part, 20+5n, of the recurrence relation (R) is a polynomial of degree 1 in n. This suggests that we might apply the Method of Undetermined Coefficients to look for a solution of the form:

(*) p(n) = c₁(.8)ⁿ + c₂ + c₃n

Substitute (*) into the recurrence relation (R):

c₁(.8)ⁿ+c₂+c₃n = .8[c₁(.8)^n-1+c_2,+c₃(n-1)] + 20 +5(n-1)

The preceding equation simplifies as follows:

c₂+c₃n = .8c₂+.8c₃n-.8c₃+20+5n-5 = (.2c₃-5)n+(.2c₂+.8c₃-15) = 0

The last equation must hold for all values of n, so:

c₃ = 5/.2 = 25
c₂ = (-.8c₃+15)/.2 = -25

This gives us the proposed general solution to (R):

p(n) = c₁(.8)ⁿ-25+25n

Now impose the initial condition (I) to evaluate c₁:

300 = p(0) = c₁-25

Thus, the proposed solution for the backsliding model is:

(**) p(n) = 325(.8)ⁿ-25+25n

The following tables of valuse created on the TI-82 show that the pollution in the lake initially decrease by nearly one-third in five years, but then begins to increase again and is back above the initial pollution level in just twelve years.

Now let's see what we can learn in general from the solution of the various parts of Examples 3.1 and 3.2. In each case, we had a linear DDS of order 1 of the form

(I) a₀ = c₀
(R) a_n = ra_n-1+g(n)

in which the non-homogeneous functon g(n) was:

1. g(n)=50 (a constant function - Example 3.1 Part 2)
2. g(n)=20 (a constant function - Example 3.2 Part 1)
3. g(n)=20(.75)^n-1 (an exponential function - Example 3.2 Part 2)
4. g(n)=20+5(n-1) (a polynomial in n)

In each case, we propsed a solution of the form

a(n) = c₁rⁿ+g^*(n)

where g^*(n) was the most general function of the same form as g(n). More specifically,

1. g(n)=50 b(n)=c₁(1.4)ⁿ+c₂
2. g(n)=20 p(n)=c₁(.8)ⁿ+c₂
3. g(n)=20(.75)^n-1 p(n)=c₁(.8)ⁿ+c₂(.75)ⁿ
4. g(n)=20+5(n-1) p(n)=c₁(.8)ⁿ+c₂+c₃n

We were then able to use the given initial condition (I) and recurrence relation (R) to determine the coefficients c₁, c₂, c₃ in such a way that a solution resulted.

This worked because the functions g(n) that constituted the non-homogeneous part of the recurrence relation all had the property that g(n) and g(n-1) had the same functional form:

g(n)=c g(n-1)=c₂
g(n)=dsⁿ g(n-1)=ds^n-1
g(n)=cn+d g(n-1)=cn+(d-c)

That feature made it possible to guess the proper form of the solution. Thus, the Method of Undetermined Coefficients is a form of "systematic guessing" that works for non-homogeneous DDS:

(I) a₀ = c
(R) a_n = ra_n-1+g(n)

when g(n) and g(n-1) have the same functional form.

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

Just Do It!

Problem 3.1
Find the solution to the following discrete dynamical systems:
1. a₀ = 3
   a_n = 2a_n-1+2 for n>0

2. b₀ = 3
   b_n = .25b_n-1-1-n

3. r₀ = 3
   r_n = r_n-1+2

4. d₀ = 1
   d_n = .65a_n-1+1.05(.5)ⁿ

Problem 3.2

A customer purchased items costing $360 with a national credit card that charges 1.5% interest per month compounded monthly.
1. Write a recurrence relation and initial conditions for b_n, the balance after n months if no further charges occur and the minimum monthly payment of $25 is made.

2. Find a general solution of the recurrence relation and the solution for this discrete dynamical system.

3. Give the value of the account after 12 months, i.e., b(12).

Problem 3.3

The temperature of a body is measured as 104^oF. It is observed that the amount the temperature changes for each period of two hours is -0.3 time the difference between the previous period's temperature and the room temperature, which is 70^oF.
1. Write a recurrence relation for t_n, the temperature of the body at the end of n 2-hour time periods.

2. Find a general and particular solution for the system and give the value of t(12), the temperature of the body after 24 hours.

3. Does this system have an equilibrium value? If so, what is it?

Problem 3.4

Radium decreases at the rate of 0.0428 percent per year.
1. What is its half-life? (A half-life of a radioactive substance is defined to be the time needed for half of the material to dissipate.

2. Write a recurrence relation to describe the decay of radium, where r_n is the amount of radium remaining after n years.

3. Suppose that one started out with 2 grams of radium. Find a solution for the discrete dynamical system illustrating this process and give the value for r(100), the amount remaining after 100 years.

Problem 3.5

A fresh water lake contains a relatively small amount, 20 tons, of chemical pollutant when a chemical plant begins operation nearby. The factory dumps 1 ton of chemical pollutant into the lake each month and an additional 1.5 tons of pollutant enter from other sources each month. Suppose that 6% of the pollutant present in the lake is dissipated each month through solar oxidation and runoff through outbound streams.
1. Write a discrete dynamical system that models the number of tons, p_n, of pollutant in the lake n months after the factory opens.

2. Find the solution of the system in (a) by the Method of Undetermined Coefficients.

3. If these conditions presist, describe as precisely as you can the predicted long term pollution levels for the lake just after the factory begins operation.

4. Suppose that the government requires all of the lake polluters to reudce their pollution by 1% per month. Under this new program, describe as precisely as you can the long-term pollution levels of the lake.

Lesson 4: Linear Discrete Dynamical Systems Of Order Two

Lesson 4:

LINEAR DYNAMICAL SYSTEMS OF ORDER TWO

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.

Introduction

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.

Solutions to Homogeneous Discrete Dynamical Systems of Order Two

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 Case of Double Roots for the Characteristic Equation

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 Case of Complex Roots for the Characteristic Equation

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)?