Discrete Dynamical Systems

Discrete dynamical systems can be used to model and analyze many real-world 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 TI-83 or TI-84 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.

Detailed Description

The purpose of this module is to familiarize mathematics teachers at the high school and community college levels with discrete dynamical systems. These systems, which can be analyzed with the tools of high school algebra, are discrete analogs to differential equation systems, which are based on calculus. As such, discrete dynamical systems can be used to introduce advanced algebra students to some of the most important ideas of calculus and differential equations. Also, discrete dynamical systems can be used to model many interesting problems on such diverse topics as: loans and annuities, population growth, radioactive decay, medication dosages, water and air pollution, and heating/cooling problems.

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 TI-82, 83.. Algebraic methods for solving difference equations are also developed.

Particular emphasis is given to seeing the relationship between such discrete dynamical systems and real-world 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:0-19-508438-1). 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 self-contained. 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 TI-82 or TI-83 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 TI-82 and TI-83 Tutorials.

The course is especially suited for Educators seeking ways to enhance their precalculus and calculus curriculum.

Required Materials

In addition to the general requirements for participating in Math Teacher Link, this module also has the following requirements:

Step by Step Instructions

Estimated Time Requirements: It is likely that teachers will require 15-25 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 15-20 hour range.

Getting Started: After you have completed and submitted your on-line registration form, you will come back to this site and go through Steps 1-6. 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 (TI-82 or TI-83) that you will be using to do this module, review the Basic TI-82 Tutorial. Working with the TI-83 is very similar.

To do the module assignments, you will need to know how to capture screen shots on your TI-82 or TI-83 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 TI-Graph Link package that is required for this module. The TI-Graph Link Tutorial will show you how to install TI-Graph 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 TI-Graph Link for this purpose, you should review this tutorial now.

Now proceed to Step 1 below.

Step #1

Even if you are familiar with the TI-82 or TI-83 calculator, you should begin by reviewing the Sequences with the TI-82 Tutorial or the Sequences with the TI-83 Tutorial, depending on the calculator that you will use to complete the module. Then proceed to Step 2.

Step #2

Study the three examples in the Introduction and then review the contents of Lesson 1: Basic Concepts and Examples. At the end of the lesson, you will find a list of problems with the title Just Do It!. Review the problems. If you are ready to solve them, proceed to Step 3. If not, review the lesson as needed until you are ready to go to Step 3.

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 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 an, we can model the chemical residue in the suits by the relationship:

    an = 0.7 an-1 + 12 for n > 0 and a0 = 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, a0 is 0.

    The following table shows the value of the residual contaminant at 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 a0=0, it follows that
    a1 = .7a0+12 = .7(0)+12 = 12,
    a2 = .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 nth year might be represented by pn, the number of births in year n is proportional to pn; that is births equals bpn. In a similar manner, the number of deaths can be represented as dpn. Hence the population in pn might be represented as pn = pn–1 + bpn–1dpn–1. This can alternatively be written as

    pn – pn–1 = (b – d)p n–1

    or pn = (1+ r) pn–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–(pn–1/C)] as a model for the change in population from one year to the next. When C equals pn–1, the expression has a value of 0 and the change in population size is 0. When C is greater than pn–1, the effect is to have a multiplier that is less than 1. When C is less than pn–1, the effect is to have a multiplier that is greater than 1. Thus the expression r[1–(pn–1/C)]. pn–1 is a good model for the change in population from one year to the next. In fact, one could write

    pnpn–l = r[1–(pn–1/C)] pn–1

    This can be written as

    pn = (1+r)pn–1 – pn–12(r/C)

    This equation is called the logistic equation, and – p n–12(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 an represent the amount of money outstanding at the end of the nth year, we can represent the loan situation as follows:

    an = 1.05an–1 - 6000 for n>0 and a0 = 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. 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?

     

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 discrete dynamical systems and how to 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 ak, ak+1, ak+2, ..., ak+j, ... that is defined as follows:
      For some positive integer p,
        (I) the first p terms of the sequence ak, ak+1, ..., ak+p-1 are given explicitly.
        (R) for all n > k+p-1, an is a given function of the preceding p terms:
        an = f(an-1, an-2, ..., an-p, n)

    Given a discrete dynamical system ak, ak+1, ak+2, ..., ak+j, ..., the function f in (R) is called the recurrence relation or the difference equation. The first p terms ak, ak+1, ..., ak+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) a0=0
      (R) an = 0.7an-1 + 12 for n>0

    2. The Population Puzzle
      (I) p0=300
      (R) pn = (1+r)pn-1 - pn-12(r/c) for n>0

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

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

  3. A system defined by the recurrence relation Rn = 3Rn-2 + 2 for n > 1 and an initial value for R0 of 5 and R1 = 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 fn = fn-3 + fn-7, where n > 6 and known values for fn 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) a0 = 10
      (R) an = 2an-1 for n > 0

    Solution:

      a0 = 10

      a1 = 2a0 = 2*10 = 20

      a2 = 2a1 = 2*20 = 40

      a3 = 2a2 = 2*40 = 80

    It is easy to guess from the calculation of a0, a1, a2, a3 by iteration that the pattern for the values of all an is:
      (*) an = 10 * 2n for all n.

    Note that the preceding formula gives an 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 a0=10 had been left unspecified, then the explicit formula for an would still be easy to guess as

      (**) an = a0 * 2n for all n

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

      (I) a0 = 10
      (R) an = 2an-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 ak, ak+1, ..., ak+j, ... is a discrete dynamical system of order p defined by:
      (I) Given initial values for ak, ak+1, ..., ak+p-1
      (R) A recurrence relation an = f(an-1, an-2, ..., an-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 c1, c2, ..., cp 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 ak, ak+1, ..., ak+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) = an = -40(.7)n + 40 for all n is a solution for the chemical spill dynamical system:
      (I) a0 = 0
      (R) an = .7an-1 + 12 for n>0

    Solution:

      Method 1: Tables of values

        Enter the following sequences into your calculator:

          un = -40(.7)n + 40
          vn = .7vn-1 + 12
          v0 = 0
        and then use the Table facility on your calculator to check that the values of un and vn 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) = an = -40(.7)n + 40 for all n

        is a solution of the discrete dynamical system:

          (I) a0 = 0
          (R) an = .7an-1 + 12 for n > 0

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

          a0 = -40(.7)0+40 = -40+40 = 0 : OK
          .7an-1+12 = (.7)[-40(.7)n-1+40]+12 = -40(.7)n+28+12 = -40(.7)n+40 = an : 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. an = an-2 + 3n + 6 for n>1 where a0=2 and a1=3.
      2. an = 2an + 3 for n>0 where a0=5.
      3. an = 3n + 6 for n>0 where a0=2.
      4. an = an-12 + 2an-2 + 3n + 6 for n>1 where a0=2 and a1=3.

    Problem 1.2

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

    Problem 1.3
    1. Use your calculator to create a table that gives strong evidence that
        (*) a(n) = an = 5(.5)n + 2n - 2
      is a solution of the discrete dynamical system:
        (I) a0=3
        (R) an = .5an-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 a25. (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 population 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 pn 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)n + 120,000 is a solution of the DDS given by the Car Loan Problem in the Introduction:

        (I) a0=20,000
        (R) an=1.05an-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.

Step #3

The Just Do It! problems in Lesson 1 are your first assignment to be turned in electronically on MTL. You will find the Assignment 1 shell file (called Assgn_1) attached below. That shell will list the Just do it! problems for Lesson 1 . Open that shell and complete the assignment according to the instructions in that shell.

Submit Assignment 1 using the Hand In link above.

AttachmentSize
Assgn_1.doc30.5 KB

Step #4

Study Lesson 2: Linear Discrete Dynamical Systems. At the end of the lesson, you will find another list of Just Do It! problems. Review the problems and when you feel that you are ready to solve them, open the Assignment 2 shell (Assgn_2 is attached below) and do the assignment according to the directions in that shell.

Submit Assignment 2 using the Handin link above.

AttachmentSize
Assgn_2.doc15.71 KB

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 an = f(an-1, an-2, ..., an-p, n) for n > k+p-1 is the recurrence relation for a discrete dynamical system of order p:

ak, ak+1, ..., ak+j, ...

The recurrence relation f is linear if there are p constants c1, c2, ..., cp and a function g(n) such that f can be written as:

an = c1an-1 + c2an-2 + ... + cpan-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 (an = .7an-1 + 12) and for the Car Loan Problem (an = 1.05an-1 - 6000) are linear; in fact, they are affine.
    2. The recurrence relations of order 1 for the Population Puzzle (pn = (1+r)pn-1 - (r/c)pn-12) is not linear.
    3. The recurrence relation for the Fibonacci sequence,
        (I) a0=1, a1=1
        (R) an = an-1 + an-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) u0=c
    (R) un=run-1 for n>0

 

or are affine and of order 1:

    (I) u0=c
    (R) vn=rvn-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) u0 = c
    (R) un = run-1 for n>0,

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

    u1 = ru0 = cr
    u2 = ru1 = cr2
    u3 = ru2 = cr3
    u4 = ru3 = cr4

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

    u(n) = un = crn 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) v0 = c
    (R) vn = rvn-1+d for n>0

is given by v(n) = vn = rn(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 un and vn 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:

      un = run-1 for n>0

    is:

      un = crn for all n

    This solution has u0=c as its initial value.

     

  • The general solution of the affine non-homogeneous recurrence relation:

      vn = rvn-1+d for n>0,

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

      vn = rn(c - d/(1-r)) + d/(1-r) for all n

    This solution has v0=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) a0=0
      (R) an = .7an-1 + 12 for n>0

    Solution:

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

      an=(.7)n(0 - 12/(1-.7)) + 12/(1-.7) = -40(.7)n+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 an 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 an 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 uk = a for all values of k when the initial value u0 is set at a . That is, uk = 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 un = f(un-1, ..., un-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) v0=c
        (R) vn=rvn-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) u0=0
      (R) un=.75un-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 u0 = 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) u0=2
      (R) un=(-.8)un-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:

      un = 0.75un-1 + 16 for n > 0 and u0 = 0.

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

    Set

      UnStart=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) u0=0
      (R) un=.5un-1-1 for n>0

       

    2. (I) u0=1
      (R) un=1.5un-1+2 for n>0

       

    3. (I) u0=-2
      (R) un=-.3un-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. un=un-1-2 where u0=4
      2. un=un-1+3 where u0=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) u0=c
          (R) un=un-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) u0=c
        (R) un = run-1 for n>0

      then u(n) can be written in the form

        u(n) = crn for all n

    Step #5

    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.

    AttachmentSize
    Assgn_3.doc15.71 KB

    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) ak, ak+1, ..., ak+p-1 are specified
        (R) an=f(an-1, ..., an-p, n)

      is important to the study of such systems, because a solution a(n) allows one to move immediately to the value of an knowing only the value of n. To find the value of an using the discrete dynamical system, one would have to work up from the initial value(s) (I) to get the value of an 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 c1,c2, ..., cp 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) a0=c0
        (R) an = ran-1 for n>0

      can be written in the form

        (*) a(n) = an = c0rn for all n

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

        (I) a0=c0
        (R) an = ran-1+b

      is given by

        a(n)=rn(c0 - (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 an=rn(c0-b/(1-r)) + b/(1-r) is a solution of the affine system

        (I) a0=c0
        (R) an = ran-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, bn for n = 10, given the recurrence relation of bn = 1.40bn-1 for n> 0 and b0 = 300. We could iterate through the values of bi 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 bn = (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 bn = 1.40bn-1 + 50 for n > 1 and b0 = 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 bn = c1rn + c2, where c1 and c2 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 bn and bn-1 would have to take on the values

        bn = 1.40n c1+ c2 and bn-1 = 1.40n-1 c1+ c2

      where the constants c1 and c2 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,

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

      can be written as

        (1.40n c1+ c2) = 1.40 (1.40n-1 c1 + c2) + 50 for n > 0

      Doing the algebraic manipulations, we can solve for c2 to obtain c2=-125, thereby getting the general solution

        bn = c1(1.40)n – 125 for all n

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

        300 = b0 = c1(1.40)0-125 = 300.

      Solving for c1, we have c1 = 425. This gives us our solution: bn = 425(1.40) n – 125. Substituting this back into the original discrete dynamical system, we see that it checks and hence bn = 425(1.40)n – 125 for all n is a solution for the discrete dynamical system bn = 1.40b n-1 + 50 for n > 0 and b0 = 300. After 10 years, this model predicts a bass population of b10=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) a0=c0
            (R) an=ran-1+b for n>0

          look for a solution of the form

            (*) a(n) = an = c1rn + c2 for all n

          where c1, c2 are constants that are determined by substituting (*) into (I) and (R) and solving the resulting equations for c1 and c2.
      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 pn 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) p0=300
        (R) pn = .8pn-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)=c1(.8)n + c2

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

        (R) c1(.8)n + c2 = .8[c1(.8)n-1+c2] + 20

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

        300 = p(0) = c1(.8)0+100

      Thus, c1=200 and

        (**) p(n) = 200(.8)n+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)n 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 an=ran-1+dsn

      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) p0=300
        (R) pn=.8pn-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) = c1(.8)n+c2(.75)n

      for appropriate choices of the coefficients c1 and c2. Substitute (*) into (R):

        c1(.8)n+c2(.75)n = .8[c1(.8)n-1+c2(.75)n-1] + 20(.75)n-1

      Simplify this equation to obtain:

        c2(.75) = .8c2+20

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

        p(n) = c1(.8)n - 400(.75)n

      Now impose the initial condition (I):

        300 = p(0) = c1-400

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

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

      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 an=ran-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) p0=300
        (R) pn=(.8)pn-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) = c1(.8)n + c2 + c3n

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

        c1(.8)n+c2+c3n = .8[c1(.8)n-1+c2,+c3(n-1)] + 20 +5(n-1)

      The preceding equation simplifies as follows:

        c2+c3n = .8c2+.8c3n-.8c3+20+5n-5 = (.2c3-5)n+(.2c2+.8c3-15) = 0

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

        c3 = 5/.2 = 25
        c2 = (-.8c3+15)/.2 = -25

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

        p(n) = c1(.8)n-25+25n

      Now impose the initial condition (I) to evaluate c1:

        300 = p(0) = c1-25

      Thus, the proposed solution for the backsliding model is:

        (**) p(n) = 325(.8)n-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) a0 = c0
        (R) an = ran-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) = c1rn+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)=c1(1.4)n+c2
      2. g(n)=20 p(n)=c1(.8)n+c2
      3. g(n)=20(.75)n-1 p(n)=c1(.8)n+c2(.75)n
      4. g(n)=20+5(n-1) p(n)=c1(.8)n+c2+c3n

      We were then able to use the given initial condition (I) and recurrence relation (R) to determine the coefficients c1, c2, c3 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)=c2
        g(n)=dsn g(n-1)=dsn-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) a0 = c
        (R) an = ran-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. a0 = 3
          an = 2an-1+2 for n>0

        2. b0 = 3
          bn = .25bn-1-1-n

        3. r0 = 3
          rn = rn-1+2

        4. d0 = 1
          dn = .65an-1+1.05(.5)n

      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 bn, 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 104oF. 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 70oF.

        1. Write a recurrence relation for tn, 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 rn 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, pn, 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.

    Step #6

    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 e-mail message to one of the instructors at: discrete@mtl.math.uiuc.edu

    AttachmentSize
    Assgn_4.doc16.4 KB
    Fin_Proj.rtf42.45 KB

    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) a0=b0, a1=b1
        (R) an=f(an-1, an-2, n)

      that are linear; that is, systems for which the recurrence relation (R) can be written as

        an=han-1+kan-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) a0=0, a1=1
        (R) an=2an-1-an-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) a0 = c
        (R) an = ran-1 for n>0

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

      Suppose that we look for solutions of the form

        (*) a(n)=an=crn

      to a homogeneous recurrence relation

        (**) an=han-1+kan-2

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

        crn = hcrn-1 + kcrn-2

      Rewrite the preceding equation in the form

        crn - hcrn-1 - kcrn-2 = crn-2(r2-hr-k) = 0

      This means that:

        If r is any root of the quadratic equation

          (C) x2-hx-k = 0

        then a(n)=an=crn is a solution of the homogeneous recurrence relation

          (R) an = han-1+kan-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) = c1rn + c0sn for all n

      where r and s are the distinct real roots to the characteristic equation and c1 and c0 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) = c1rn + c0sn; a(n–1) = c1rn–1 + c0sn–1; and a(n–2) = c1rn–2 + c0sn–2.

      Substituting these expressions back into the recurrence relation we have:

      c1rn + c0sn = h(c1rn–1 + c0sn–1) + k(c1rn–2 + c0sn–2).

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

      c1rn–2(r2hrk) + c0sn–2(s2hsk) = 0.

      But this relationship will be identically equal to 0 for all values of n if and only if both r2hrk and s2hsk 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 x2hxk = 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) x2-hx-k=0

          for a second order, homogeneous recurrence relation

            (R) an=han-1+kan-2 for n>0,

          then

            a(n)=c1rn+c2sn

          is the general solution of the equation, where c1 and c2 are constants determined by initial values.

      Example 4.2: Solve the discrete dynamical system

        (I) F0 = 1, F1 = 1
        (R) Fn = Fn-1 + Fn-2 for n>1

      that defines the Fibonacci sequence

        { Fn } = { 1,1,2,3,5,8,13,21,34,... }

      Solution: The characteristic equation for the system is

        x2-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) = c1[(1+51/2)/2]n + c2[(1-51/2)/2]n

      Now impose the initial conditions F0=1 and F1=1 to obtain the equations:

        1 = c1 + c2
        1 = c1(1+51/2)/2 + c2(1-51/2)/2

      The preceding equations can be solved for c1, c2 to obtain the following solution for the Fibonacci system

        F(n) = (1/2(5)1/2)[(1+51/2)/2]n+1 - (1/2(5)1/2)[(1-51/2)/2]n+1

        F(n) = (1/2n+151/2)[(1+51/2)n+1 -(1-51/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) a0=0, a1=1
        (R) an=2an-1-an-2 for n>1

      has the characteristic equation

        x2-2x+1 = 0

      This equation can be written as

        (x-1)2 = 0

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

        an = c11n

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

        a0=0, a1=1.

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

        an = c2n 1n

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

        c2n 1n = 2c2(n-1)1n-1 - c2(n-2)1n-2
        c2n = 2c2n - 2c2 - c2n + 2c2
        c2n = c2n : It checks!

      This means that

        an = a(n) = c11n + c2n 1n

      is a general solution of the recurrence relation

        an = 2an-1 - an-2 for n>1

      for any choice of constants c1 and c2.

      Now impose the initial conditions:

        0 = a0 = c110 + c2(0) (1n) = c1
        1 = a1 = c111 + c2(1) (11) = c1 + c2

      Thus, c1=0 and c2=1, so the solution of the given discrete dynamical system is

        a(n) = (0)1n + (n)(1n) = 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

          an = han-1 + kan-2

        of order 2 has a characteristic equation:

          x2-hx-k = 0

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

          a(n) = an = c1rn + c2nrn

        where c1 and c2 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

        x2-hx-k = 0

      then an=c2nrn satisfies the recurrence relation:

        an = han-1 + kan-2 for n>1

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

        c2nrn = h(c2[n-1]rn-1) + k(c2[n-2]rn-2)
        c2nrn = hc2nrn-1 - hc2rn-1 + kc2nrn-2 - 2kc2rn-2
        c2nrn-2[r2-hr-k] + c2rn-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 x2-hx-k=0 then r=h/2 and h2+4k=0. Thus, an=c2nrn 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) a0 = 1, a1 = 2
        (R) an = an-1 - an-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:

        a0 = 1
        a1 = 2
        a2 = a1 - a0 = 1
        a3 = a2 - a1 = -1
        a4 = a3 - a2 = -2
        a5 = a4 - a3 = -1
        a6 = a5 - a4 = 1

      The characteristic equation for (R) is:

        x2-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) = c1rn + c2sn for all n

      Thus, in this case, the general solution is

        a(n) = c1(1/2 + 31/2i/2)n + c2(1/2 - 31/2i/2)n 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 a0=1 and a1=2 to obtain the equations

        1 = a0 = c1 + c2
        2 = a1 = c1(1/2 + 31/2i/2) + c2(1/2 - 31/2i/2)

      These equations can be solved for c1 and c2 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-31/2i/2)(1/2+31/2i/2)n + (1/2+31/2i/2)(1/2-31/2i/2)n

      Let's check the first few values:

        a0 = (1/2-31/2i/2) + (1/2+31/2i/2) = 1
        a1 = (1/2-31/2i/2)(1/2+31/2i/2) + (1/2+31/2i/2)(1/2-31/2i/2)
        a1 = (1/4+3/4) + (1/4+3/4) = 2
        a2 = (1/2-31/2i/2)(1/2+31/2i/2)2 + (1/2+31/2i/2)(1/2-31/2i/2)2
        a2 = (1/2-31/2i/2)(-1/2+31/2i/2) + (1/2+31/2i/2)(-1/2-31/2i/2)
        a2 = (-1/4+3/4) + (-1/4+3/4) = 1, etc.

      It's working!

      Summary:

        If the characteristic equation

          x2-hx-k = 0

        of a homogeneous linear DDS

          (I) a0 = c, a1 = d
          (R) an = han-1 + kan-2 for n>1

        has complex conjugate roots

          r = a ± ib

        then the general solution of (R) is

          a(n) = c1(a + ib)n + c2(a - ib)n for all n

        where c1 and c2 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 = (a2+b2)1/2, q = Arctan (b/a)

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

        zn = (a + ib)n = rn(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 zn:

      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) = rn(d1cos(nq) + d2sin(nq))

      where d1 and d2 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 ± 31/2i/2 = cos(p/3) + (i)sin (p/3)

      Therefore, the real general solution of that system is

        a(n) = [d1cos(np/3) + d2sin(np/3)] for all n

      To compute the values of d1 and d2 that are determined by the initial values, note that

        1 = a(0) = (1)d1 + (0)d2
        2 = a(1) = cos(p/3)d1 + sin(p/3)d2
        2 = a(1) = (1/2)d1 + (31/2/2)d2

      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) + 31/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) a0 = -7, a1 = 38
          (R) an = 5an-1 - 6an-2 + 2*5n

      Solution:

        The homogeneous recurrence relation corresponding to (R) is

          (R*) an = 5an-1 - 6an-2

        The characteristic equation of (R*):

          x2 - 5x + 6 = 0

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

          an = c12n + c23n 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

          an = c(5n) for all n

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

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

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

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

          -50+6c = 0

          c = 50/6 = 25/3

        Therefore

          an = (25/3)5n for all n

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

          an = c12n + c23n + (25/3)5n for all n

        where c1 and c2 are constants detmerined by the initial conditions (I).

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

          -7 = a(0) = c1 + c2 + 25/3
          38 = a(1) = 2c1 + 3c2 + 125/3

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

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

    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) an = -an-1 + 6an-2

        for each of the following sets of initial conditions

        1. (I) a0=1, a1=2
        2. (I) a0=1, a1=-3
        3. (I) a0=1, a1=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) a0=1, a1=2
          (R) an = 2an-1 + 2an-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) an = -an-1 - (1/4)an-2

        Then find the solution that corresponds to the initial values

          (I) a0=1, a1=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 Sn 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 S1=1, S2=2, S3=3, S4=5 by just listing all of the possible messages in each case.

        2. Explain why the following recurrence relation holds for Sn:

            Sn = Sn-1 + Sn-2 for n>2

        3. Find a formula for Sn as a function of n; that is, solve the discrete dynamical system:

            (I) S1 = 1, S2 = 2
            (R) Sn = Sn-1 + Sn-2 for n>2

      Problem 4.5

        1. Find the general solution of the recurrence relation:

            (R) an = 7an-1 - 10an-2 for n>1

        2. Find the solution of the DDS consisting of the recurrence relation (R) and the initial conditions

            (I) a0=2, a1=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"

            un = an / an-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)?