Lecture Notes on Difference Equations

Lecture Notes on Difference Equations

Arne Jensen Department of Mathematical Sciences Aalborg University, Fr. Bajers Vej 7G

DK-9220 Aalborg ?, Denmark Copyright ?2011 by Arne Jensen

All rights reserved

Version 1, July 18, 2011

Contents

1 Introduction

1

2 Prerequisites

1

3 Notation and basic concepts

2

4 First order difference equations

5

4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 Difference calculus

11

6 Second order linear difference equations

12

6.1 The constant coefficient case: Homogeneous equation . . . . . . . . . . . . . . . 14

6.2 The constant coefficient case: Inhomogeneous equation . . . . . . . . . . . . . . 18

6.3 The variable coefficient case: Homogeneous equation . . . . . . . . . . . . . . . . 22

6.4 The variable coefficient case: Inhomogeneous equation . . . . . . . . . . . . . . . 23

6.5 Second order difference equations: Linear algebra . . . . . . . . . . . . . . . . . . 25

7 Higher order linear difference equations

28

8 Systems of first order difference equations

31

8.1 Second order difference equation as a system . . . . . . . . . . . . . . . . . . . . . 35

8.2 Further results on matrix powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

9 Supplementary exercises

44

9.1 Trial Exam December 2010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

9.2 Exam January 2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

9.3 Exam February 2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

References

50

List of Figures

4.1 Point plot of the solution (4.10). Points connected with blue line segments . . 9 4.2 Point plot of the solution to (4.11). Points connected with blue line segments . 9

List of Tables

6.1 Method of undetermined coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . 21

i

1 Introduction

These lecture notes are intended for the courses "Introduction to Mathematical Methods" and "Introduction to Mathematical Methods in Economics". They contain a number of results of a general nature, and in particular an introduction to selected parts of the theory of difference equations.

2 Prerequisites

The reader is assumed to have the basic knowledge of mathematics provided by the Danish high school system. This includes a basic understanding of mathematical notation and familiarity with reading a mathematical text. These notes are written is the manner of an ordinary mathematical text. This means the the density of information on each page is quite high.

Experience shows that one aspect of mathematical notation is often not understood, or worse, misunderstood. This concerns the order of mathematical operations. We start with numbers. To make statements obvious we use a centered dot to denote the multiplication of two numbers, as in 4?7. One of the rules states that multiplication takes precedence over addition and subtraction. This means that 3+4?7 = 3+28 = 31, i.e. multiplication is carried out before addition. The same rule applies to division, such that 3+8/4 = 3+2 = 5. Powers and roots take precedence over multiplication and division. Thus 4 + 5 - 2 = 9 - 2 = 3 - 2 = 1.

Precedence can be changed using parenthesis. Thus 3 + 4 ? 7 = 31, but (3 + 4) ? 7 = 49. The rules can be summarized as follows. The order of precedence is

1. terms inside parenthesis

2. exponents and roots

3. multiplications and divisions, from left to right

4. additions and subtractions, from left to right

Here is a longer example:

3 - 4 ? 2 + 32/(2 + 1) = 3 - 4 ? 2 + 32/3 = 3 - 4 ? 2 + 9/3 = 3 - 8 + 9/3 = 3 - 8 + 3 = -5 + 3 = -2.

The same rules apply to symbolic expressions, for example a polynomial of degree 3:

a3x3 + a2x2 + a1x + a0.

Note that here multiplication is shown by juxtaposition of symbols. The same rules apply in many programming languages, although some languages have

their own rules. One particular case is the unary operator -. In mathematics the unary operator minus has the same order of precedence as addition. This is in contrast to some programmable calculators and to Microsoft excel. To illustrate difference, consider -32. In mathematics the result is -9, since first 3 is squared and then the sign is changed. In

1

e.g. excel the result is 9, since it is -3 that is squared. In these notes we always use the mathematical rule for the unary operator minus. In solving problems you must always use the mathematical rule.

Some additional information can be found in [5]

3 Notation and basic concepts

The positive integers 1, 2, 3, . . . are denoted by N. The non-negative integers are denoted by N0. All integers are denoted by Z. The rational numbers are denoted by Q . The real numbers are denoted by R. We have the following obvious inclusions

N N0 Z Q R.

All inclusions are strict. The main object of study in the theory of difference equations is sequences. A sequence

of real numbers, indexed by either Z or N0, is written in either of two ways. It can be written as xn or as x(n). The second notation makes it clear that a sequence is a function from either Z or N0 to R. We always use the notation x(n) for a sequence. Thus in these notes x1 and x2 are used to denote two sequences, and not two entries in one sequence.

There is one property of the set N0 which is important. The set is well-ordered, which means that any non-empty subset of N0 contains a smallest element.

Sums play an important role in our presentation of the results on difference equations. Here are some concrete examples.

4

5

1 + 2 + 3 + 4 = n = 10 and 22 + 32 + 42 + 52 = n2 = 54.

n=1

n=2

In general, the structure is

nlast

x(n)

n=nfirst

Here nfirst is called the lower limit and nlast the upper limit. x(n) is called the summand. It is a function of n, which we denote by x(n).

Our results are sometimes expressed as indefinite sums. Here are two examples.

N n = N(N + 1) and N n2 = N(N + 1)(2N + 1) .

n=1

2

n=1

6

One important question is how to prove such general formulas. The technique used is called proof by induction. We will give a simplified description of this technique. We have a certain statement, depending on an integer n N. We would like to establish its validity for all n N. The proof technique comprises two steps.

1. Basic step. Prove that the statement holds for n = 1.

2. Induction step. Prove that if the statement holds for n, then it also holds when n is replaced by n + 1.

2

Verification of these two steps constitutes the proof of the statement for all integers n N. Let us illustrate the technique. We want to prove the formula

N n = N(N + 1) for all N N.

n=1

2

For the first step we take N = 1. The formula then reads

1

=

1(1

+

1) ,

2

which is true. For the second step we assume that the formula is valid for some N and consider the left hand side for N + 1.

N +1

N

N(N + 1)

n = n + (N + 1) =

+(N + 1).

n=1

n=1

2

The second equality follows from our assumption. We now rewrite this last expression.

N (N

+

1)

+

N

+

1

=

N (N

+

1)

+

2(N

+

1)

=

(N

+

1)(N

+

2) .

2

2

2

Thus we have shown that

N +1

(N + 1)((N + 1) + 1)

n=

,

n=1

2

i.e. the formula holds with N replaced by N + 1, and the proof is finished.

We also need a convenient notation for products. Here are two examples.

5

4

1 ? 2 ? 3 ? 4 ? 5 = n = 120 and 3 ? 5 ? 7 ? 9 = (2n + 1) = 945.

n=1

n=1

The terminology is analogous the the one used for sums. In particular, we will be using

indefinite products. The product

N

n

n=1

appears so often that is has a name. It is called the factorial of N, written as N!. So by

definition

N

N! = n.

n=1

It is a number that grows rapidly with N, as can be seen in these examples.

10! = 3628800, 20! = 2432902008176640000, 30! = 265252859812191058636308480000000.

We have the convention that

0! = 1.

The general structure of a product is

nlast

x(n).

n=nfirst

3

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download