Discrete dynamical systems can be used to model and analyze many realworld problems including population growth, compound interest and annuities, radioactive decay, pollution control, and medication dosages. Such problems are usually delayed until calculus; however, the discrete dynamical systems approach uses only high school advanced algebra. Teachers who complete this module will be able analyze a variety of discrete dynamical systems using the TI83 or TI84 calculators (or any other calculator with similar graphing and sequence capabilities). They will also learn how to integrate this material into advanced algebra, precalculus, and calculus courses. This course was developed at our MTL partner institution, Illinois State University. Credit: 1 grad. sem. hr.
Common Core Standards for Mathemtical Practice that are emphasized include:
Discrete Dynamical Systems for Teachers was written by Professor John Dossey of Illinois State University and posted on MTL in September, 1997. It was revised by Tony Peressini in July of 1998.
Teachers will learn how to set up and solve such problems and will also learn how to integrate content on discrete dynamical systems into their advanced algebra, precalculus and calculus courses.
A discrete dynamical system consists of a recurrence relation (or difference equation) describing some relationship, pure or applied, with a given set of initial conditions. The course examines a variety of discrete dynamical systems using an iterative and graphical approach facilitated by the use of calculators such as the TI82, 83.. Algebraic methods for solving difference equations are also developed.
Particular emphasis is given to seeing the relationship between such discrete dynamical systems and realworld applications. Such applications are used to motivate the mathematical ideas, and both the illustrative examples and the homework exercises encourage those participating in the module to apply their knowledge to interesting and realistic settings. Through the experiences gained via these activities, the concepts "limit" and "solution" take on new meaning.
This course draws on the approach to Discrete Dynamical Systems employed in the Department of Mathematical Sciences at the U.S. Military Academy at West Point. The faculty there have been using this approach as an introduction to the calculus strand since the late 1980s. The material parallels the approach taken in the text Discrete Dynamical Modeling by James Sandefur (New York, NY: Oxford University Press, 1993. ISBN:0195084381). This approach, which bridges the gap between precalculus and the calculus, analyzes the sequences of values that result from iterating difference equations under varying initial values. These equations, by their very nature describe the shifts from one, or more, state(s) to another. As such, they are the discrete analog to differential equations.
This module is selfcontained. You do not have to buy any additional textual
materials. You do need to set aside ample time to wrestle with the
problems and the content presented. Your TI82 or TI83 calculator will
become a good friend
before the module is over, in new ways that you may have never imagined
possible before. If you are not familiar with the operation of the
sequence mode giving dot output, the web format for the window, or the use
of tables, you can acquire these skills through the Interactive TI82 and
TI83 Tutorials.
The course is especially suited for Educators seeking ways to enhance
their precalculus and calculus curriculum.
In addition to the general requirements for participating in Math Teacher Link, this module also has the following requirements:
Estimated Time Requirements: It is likely that teachers will require 1525 hours to study the lessons and complete the lesson assignments for this module. Those teachers enrolled for Graduate Credit will also be required to complete a Final Project that integrates the module content into a unit for one of their classes. The time required to complete the Final Project will vary, but should fall generally in the 1520 hour range.
Getting Started: After you have completed and submitted your online registration form, you will come back to this site and go through Steps 16. Some steps will contain assigment shells, which are Microsoft Word documents, that you will use to coplete and submit lesson assignents for this module. If you are enrolled for graduate credit, there will be a final project shell (see step 6) that you will use to organize and submit your final project. You should open these documents and scan their contents briefly. If you are not very familiar with the calculator (TI82 or TI83) that you will be using to do this module, review the Basic TI82 Tutorial. Working with the TI83 is very similar.
To do the module assignments, you will need to know how to capture screen shots on your TI82 or TI83 calculator and transfer them to your computer so that you can paste them into the Assignment shells, which are MS Word documents in your download folder for this module. This is quite easy to do with the TIGraph Link package that is required for this module. The TIGraph Link Tutorial will show you how to install TIGraph Link on your Mac or Windows machine and also show you how to do these screen captures and insert them in other documents on your computer. If you are not already using TIGraph Link for this purpose, you should review this tutorial now.
Now proceed to Step 1 below.
Even if you are familiar with the TI82 or TI83 calculator, you should begin by reviewing the Sequences with the TI82 Tutorial or the Sequences with the TI83 Tutorial, depending on the calculator that you will use to complete the module. Then proceed to Step 2.
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 range 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 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_{n1} + 12 for n > 0 and a_{0} = 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_{0} is 0.
The following table shows the value of the residual contaminant a_{t} in the suit after t hours:
 
 

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
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
This can be written as
This equation is called the logistic equation, and – p _{n–1}^{2}(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 
p_{n} 
p_{n } 
p_{n } 
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_{0} = 20,000.
That is, the loan balance in the n^{th} 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.


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 
a_{n}  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 
a_{n}  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. Some questions asked are; 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 our knowledge of mathematics to understand, predict, and control what happens in each of these settings?
Objectives of This Lesson:
1.1 Basic Definitions:
Example 1.3:
Solution:
a_{0} = 10
a_{1} = 2a_{0} = 2*10 = 20
a_{2} = 2a_{1 }= 2*20 = 40
a_{3} = 2a_{2 }= 2*40 = 80
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_{0}=10 had been left unspecified, then the explicit formula for a_{n} would still be easy to guess as
The formula (*) is the "solution" of the discrete dynamical system defined by:
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
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_{1}, c_{2}, ..., 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
Solution:
Method 1: Tables of values
Enter the following sequences into your calculator:
If you scroll down the table further on your calculator, you will see that u_{n} and v_{n} continue to agree. This is strong evidence that v_{n} is a solution of the chemical spill problem. 
Method 2: Algebraic proof.
by simply checking algebraically that (*) satisfies (I) and (R):
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.2
Problem 1.4
Problem 1.5
Problem 1.6
Submit Assignment 1 using the Hand In link above.
Attachment  Size 

Assgn_1.doc  30.5 KB 
Submit Assignment 2 using the Handin link above.
Attachment  Size 

Assgn_2.doc  15.71 KB 
Objectives of This Lesson:
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
a_{k}, a_{k+1}, ..., a_{k+j}, ...
The recurrence relation f is linear if there are p constants c_{1}, c_{2}, ..., c_{p} and a function g(n) such that f can be written as:
a_{n} = c_{1}a_{n1} + c_{2}a_{n2} + ... + c_{p}a_{np} + g(n)
Examples 2.2
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:
or are affine and of order 1:
where d is nonzero 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:
just iterate the recurrence relation (R) and substitute the initial value:
It appears from these calculations that the solution of the given system is:
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, nonhomogeneous discrete dynamical system:
is given by v(n) = v_{n} = r^{n}(c  d/(1r)) + d/(1r) 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:
is:
This solution has u_{0}=c as its initial value.
where d is nonzero and r is not equal to 1 is:
This solution has v_{0}=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 nonhomogeneous linear recurrence relations in Lesson 3.
Example 2.3
Solution:
This is an affine system with initial value a_{0}=0, r=.7, d=12, so the preceding result states that the solution is
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)^{n} 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_{0} 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_{n1}, ..., u_{np}, 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 firstorder affine system
has an equilibrium value of d/(1r) 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 nonlinear a dynamical system is, the more equilibrium values it may have.
Cobweb Graphs for Discrete Dynamical Systems
Example 2.4:
Construct the cobweb graph of the affine system defined by:
Solution:
The cobweb graph for this system is shown below.
But how was this graph constructed? Consider mapping of the initial value u_{0} = 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
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 TI82 with a few keystrokes. First, press Y= to enter the recurrence relation representing a discrete dynamical system:
Enter the WINDOW editor by pressing on the WINDOW key beneath the screen.
Set
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 rightarrow 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
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!
do the following with your calculator:
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:
the value of r is 1, so the solution formulas given in this lesson do not apply.
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),
Problem 2.5
Use mathematical induction to prove that u(n) is a solution of the homogeneous system
then u(n) can be written in the form
Study Lesson 3: Constructing Solutions To Linear Discrete Dynamical Systems. Review the Just Do It! problems at the end of that lesson and when you feel that you are ready to solve them, open the Assignment 3 shell (Assgn_3 attached below) and do the assignment according to the directions in that shell.
Submit Assignment 3 using the Handin link above.
Attachment  Size 

Assgn_3.doc  15.71 KB 
Lesson 3: 
Objectives of This Section:
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+p1} are specified
(R) a_{n}=f(a_{n1}, ..., a_{np}, n)
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_{1},c_{2}, ..., 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:
can be written in the form
We also stated, but did not prove, that the solution of the affine system of order 1
is given by
The Method of Undetermined Coefficients with Systems
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, nonhomogeneous 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_{n1} for n> 0 and b_{0} = 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)^{n}. 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_{n1 }+ 50 for n > 1 and b_{0} = 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
(R) b_{n}=1.40b_{n1}+50 for n>1 Looking at a graph of the bass population using the TI82, we see that the population seems to be modeled by an exponential function with a positive yintercept. 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_{1}r^{n} + c_{2}, where c_{1} and c_{2} 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_{n1} would have to take on the values
where the constants c_{1} and c_{2} 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,
can be written as
To find the particular solution determined by the initial condition b_{0} = 300, we now evaluate the general solution for b_{0} = 300. This gives us
Summary of the Method of Undetermined Coefficients for Affine Discrete Dynamical Systems
(I) a_{0}=c_{0}
(R) a_{n}=ra_{n1}+b for n>0
(*) a(n) = a_{n} = c_{1}r^{n} + c_{2} for all n
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:
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
where the coefficients are determined by imposing the conditions (I) and (R):
By simplifying the preceding equation, we see that c_{2}=.8c_{2}+20; that is, c_{2}=100. This means that p(n)=c_{1}(.8)^{n}+100 is the general solution of (R). Now impose the condition (I) to evaluate c_{1}:
Thus, c_{1}=200 and
is the solution of the discrete dynamical system.
If you tabulate the function (**) on a TI82, 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)^{n} approaches 0 as n increases, the constant term, 100, forces p(n) to exceed 100 for all n.
Solution: The modified program is modeled by the discrete dynamical system:
This is a linear DDS in which the nonhomogeneous term, 20(.75)^{n1}, 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:
for appropriate choices of the coefficients c_{1} and c_{2}. Substitute (*) into (R):
Simplify this equation to obtain:
Therefore, c_{2} = 20/(.05) = 400, and so the proposed general solution of (R) is
Now impose the initial condition (I):
Thus c_{1}=700 and so the proposed solution of this modified DDS is
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 TI82 and displayed at right shows that this modified pollution control program will reduce lake pollution by nearly twothirds 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. 
Solution: The discrete dynamical system that models this "backsliding" on the pollution control program is:
The nonhomogeneous 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:
Substitute (*) into the recurrence relation (R):
The preceding equation simplifies as follows:
The last equation must hold for all values of n, so:
This gives us the proposed general solution to (R):
Now impose the initial condition (I) to evaluate c_{1}:
Thus, the proposed solution for the backsliding model is:
The following tables of valuse created on the TI82 show that the pollution in the lake initially decrease by nearly onethird 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
in which the nonhomogeneous functon g(n) was:
In each case, we propsed a solution of the form
where g^{*}(n) was the most general function of the same form as g(n). More specifically,
We were then able to use the given initial condition (I) and recurrence relation (R) to determine the coefficients c_{1}, c_{2}, c_{3} in such a way that a solution resulted.
This worked because the functions g(n) that constituted the nonhomogeneous part of the recurrence relation all had the property that g(n) and g(n1) had the same functional form:
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 nonhomogeneous DDS:
when g(n) and g(n1) 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.2
Problem 3.3
Problem 3.4
Problem 3.5
Study Lesson 4: Linear Discrete Dynamical Systems Of Order Two . When you feel that you are ready to solve the Just Do It! problems at the end of Lesson 4, open the Assignment 4 shell (Assgn_4 attached below) and do the assignment according to the directions in that shell.
Submit Assignment 4 using the Handin link above.
If you are enrolled for Continuing Education Credit, you have now completed the module requirements. Congratulations! You should receive official notification of completion of the module from the Division of Extramural Programs within three weeks after we complete our review of your 4 module assignments.
If you are enrolled for Graduate Credit, you now have the opportunity to apply what you have learned to your own teaching by completing the required Final Project.
The specific ingredients for a Final Project are listed in the "Fin_Proj.rtf" file that you can download in the attachment area near the bottom of this page. However, there is a great deal of latitude in the choice of topic for your Final Project. We want it to be a classroom unit that interests you and that will be useful for your teaching, and, of course, it should make significant use of what you have learned about discrete dynamical systems or the sequence capabilities of your calculator.
You might have already thought of good classroom unit for your Final Project as you were learning the lesson material for the module. If you would like to discuss your plans, or perhaps ask for some suggestions, we encourage you to call us using the MTL 800  number. In any case:
You need to send us a brief description of your Final Project plans in an email message to one of the instructors at: discrete@mtl.math.uiuc.edu
Attachment  Size 

Assgn_4.doc  16.4 KB 
Fin_Proj.rtf  42.45 KB 
Lesson 4:  LINEAR DYNAMICAL SYSTEMS OF ORDER TWO 
Objectives of This Lesson:
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 secondorder discrete dynamical systems:
(I) a_{0}=b_{0}, a_{1}=b_{1}
(R) a_{n}=f(a_{n1}, a_{n2}, 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}=0, a_{1}=1
(R) a_{n}=2a_{n1}a_{n2} for n>1
n 
a_{n} 
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:
We saw that the solution for this system can be written as a(n)=cr^{n} for all n.
Suppose that we look for solutions of the form
to a homogeneous recurrence relation
of order 2. By substitution, you can see that (*) will be a solution of (**) provided that r satisfies:
Rewrite the preceding equation in the form
This means that:
then a(n)=a_{n}=cr^{n} is a solution of the homogeneous recurrence relation
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 firstorder recurrence relation and solution. A conjecture for a solution to this secondorder homogeneous system of order 2 might be
where r and s are the distinct real roots to the characteristic equation and c_{1 }and c_{0} are constants derivable from the recurrence relation and initial values.
The solution in this case, like in the firstorder 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_{1}r^{n} + c_{0}s^{n}; a(n–1) = c_{1}r^{n–1} + c_{0}s^{n–1}; and a(n–2) = c_{1}r^{n–2} + c_{0}s^{n–2}.
Substituting these expressions back into the recurrence relation we have:c_{1}r^{n} + c_{0}s^{n} = h(c_{1}r^{n–1} + c_{0}s^{n–1}) + k(c_{1}r^{n–2} + c_{0}s^{n–2}).
If we simplify this equation, we find that it can be written as:c_{1}r^{n–2}(r^{2} – hr – k) + c_{0}s^{n–2}(s^{2} – hs – k) = 0.
But this relationship will be identically equal to 0 for all values of n if and only if both r^{2} – hr – k and s^{2} – 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^{2} – 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.
for a second order, homogeneous recurrence relation
then
is the general solution of the equation, where c_{1} and c_{2} are constants determined by initial values.
(I) F_{0} = 1, F_{1} = 1
(R) F_{n} = F_{n1} + F_{n2} for n>1
Solution: The characteristic equation for the system is
which has roots
r_{1} = (1+5^{1/2})/2  r_{2} = (15^{1/2})/2 
Now impose the initial conditions F_{0}=1 and F_{1}=1 to obtain the equations:
The preceding equations can be solved for c_{1}, c_{2} to obtain the following solution for the Fibonacci system
F(n) = (1/2^{n+1}5^{1/2})[(1+5^{1/2})^{n+1} (15^{1/2})^{n+1}]
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}=0, a_{1}=1
(R) a_{n}=2a_{n1}a_{n2} for n>1
This equation can be written as
so it has a double root x=1. This means that
is a solution of the recurrence relation (R) of the system for any choice of the constant. However, no choice of c_{1} will yield the initial values
Notice that a second solution of this recurrence relation can be obtained by multiplying this first solution by n; that is
is also a solution! To see this, just substitute this expression into the recurrence relation a_{n} = 2a_{n1}  a_{n2}:
This means that
is a general solution of the recurrence relation
for any choice of constants c_{1} and c_{2}.
Now impose the initial conditions:
Thus, c_{1}=0 and c_{2}=1, so the solution of the given discrete dynamical system is
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:
a_{n} = ha_{n1} + ka_{n2}
of order 2 has a characteristic equation:
x^{2}hxk = 0
with a double root x=r, then the general solution of the recurrence relation is
a(n) = a_{n} = c_{1}r^{n} + c_{2}nr^{n}
where c_{1} and c_{2} 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^{2}hxk = 0
then a_{n}=c_{2}nr^{n} satisfies the recurrence relation:
a_{n} = ha_{n1} + ka_{n2} for n>1
for any choice of c_{2}. This is done by direct substitution and simplification as follows:
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^{2}hxk=0 then r=h/2 and h^{2}+4k=0. Thus, a_{n}=c_{2}nr^{n} is a solution of the recurrence relation.
Example 4.3: Find the first 7 values determined by the discrete dynamical system
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:
The characteristic equation for (R) is:
This equation has complex conjugate roots:
r = 1/2 + 3^{1/2}i/2  s = 1/2  3^{1/2}i/2 
Thus, in this case, the general solution is
(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_{0}=1 and a_{1}=2 to obtain the equations
These equations can be solved for c_{1} and c_{2} to obtain
c_{1} = 1/2  3^{1/2}i/2  c_{2} = 1/2 + 3^{1/2}i/2 
Let's check the first few values:
It's working!
Summary:
of a homogeneous linear DDS
has complex conjugate roots
then the general solution of (R) is
where c_{1} and c_{2} 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:
where r = (a^{2}+b^{2})^{1/2}, q = Arctan (b/a)
Then, as we have seen above, the sequence of complex numbers defined by:
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(z_{n}) = r^{n}cos(nq)  Im(z_{n}) = r^{n}sin(nq) 
where d_{1} and d_{2} 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:
Therefore, the real general solution of that system is
To compute the values of d_{1} and d_{2} that are determined by the initial values, note that
These equations have the solutions
d_{1} = 1  d_{2} = 3^{1/2} 
The following example shows that the Method of Undetermined Coefficients can be used for nonhomogeneous linear discrete dynamical systems of order 2 in essentially the same way as in Lesson 3 for systems of order 1.
Example 4.4:
Solution:
The characteristic equation of (R^{*}):
has roots x=2 and x=3. Consequently the general solution of (R^{*}) is
Based on the Method of Undetermined Coefficients for DDS's of order 1, we now seek a solution of the nonhomogeneous recurrence relation (R) of the form
where c is an appropriate constant determined by substitution into (R) as follows:
(c2)(5^{n})  5c(5^{n1}) + 6c(5^{n2}) = 0
[25(c2)  25c + 6c](5^{n2}) = 0
50+6c = 0
c = 50/6 = 25/3
Therefore
is a particular solution of (R) and so the general solution of (R) is
where c_{1} and c_{2} are constants detmerined by the initial conditions (I).
Now impose the initial conditions (I) to obtain the equations
This pair of equations has the solution c_{1}=127/3 and c_{2}=27, so the solution of the given DDS is:
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!
for each of the following sets of initial conditions
In each case, include a screenshot of a table of the first 6 values in the space below the solution formula.
Problem 4.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
Then find the solution that corresponds to the initial values
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:
Problem 4.5
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?