2.3 Recurrence relations

Back

DEFINITION 2.3.1 (The identity matrix) The n £ n matrix In =

[±ij ], de¯ned by ±ij = 1 if i = j; ±ij = 0 if i 6= j, is called the n £ n identity

matrix of order n. In other words, the columns of the identity matrix of

order n are the unit vectors E1; ¢ ¢ ¢ ;En, respectively.

For example, I2 =

·

1 0

0 1

¸

.

THEOREM 2.3.1 If A is m £ n, then ImA = A = AIn.

DEFINITION 2.3.2 (k{th power of a matrix) If A is an n£n matrix,

we de¯ne Ak recursively as follows: A0 = In and Ak+1 = AkA for k ¸ 0.

For example A1 = A0A = InA = A and hence A2 = A1A = AA.

The usual index laws hold provided AB = BA:

1. AmAn = Am+n, (Am)n = Amn;

2. (AB)n = AnBn;

3. AmBn = BnAm;

4. (A + B)2 = A2 + 2AB + B2;

5. (A + B)n =

Xn

i=0

¡n

i

¢

AiBn¡i;

6. (A + B)(A ¡ B) = A2 ¡ B2.

We now state a basic property of the natural numbers.

AXIOM 2.3.1 (PRINCIPLE OF MATHEMATICAL INDUCTION)

If for each n ¸ 1; Pn denotes a mathematical statement and

(i) P1 is true,

32 CHAPTER 2. MATRICES

(ii) the truth of Pn implies that of Pn+1 for each n ¸ 1,

then Pn is true for all n ¸ 1.

EXAMPLE 2.3.1 Let A =

·

7 4

¡9 ¡5

¸

: Prove that

An =

·

1 + 6n 4n

¡9n 1 ¡ 6n

¸

if n ¸ 1:

Solution. We use the principle of mathematical induction.

Take Pn to be the statement

An =

·

1 + 6n 4n

¡9n 1 ¡ 6n

¸

:

Then P1 asserts that

A1 =

·

1 + 6 £ 1 4 £ 1

¡9 £ 1 1 ¡ 6 £ 1

¸

=

·

7 4

¡9 ¡5

¸

;

which is true. Now let n ¸ 1 and assume that Pn is true. We have to deduce

that

An+1 =

·

1 + 6(n + 1) 4(n + 1)

¡9(n + 1) 1 ¡ 6(n + 1)

¸

=

·

7 + 6n 4n + 4

¡9n ¡ 9 ¡5 ¡ 6n

¸

:

Now

An+1 = AnA

=

·

1 + 6n 4n

¡9n 1 ¡ 6n

¸ ·

7 4

¡9 ¡5

¸

=

·

(1 + 6n)7 + (4n)(¡9) (1 + 6n)4 + (4n)(¡5)

(¡9n)7 + (1 ¡ 6n)(¡9) (¡9n)4 + (1 ¡ 6n)(¡5)

¸

=

·

7 + 6n 4n + 4

¡9n ¡ 9 ¡5 ¡ 6n

¸

;

and \the induction goes through".

The last example has an application to the solution of a system of re-

currence relations:

2.4. PROBLEMS 33

EXAMPLE 2.3.2 The following system of recurrence relations holds for

all n ¸ 0:

xn+1 = 7xn + 4yn

yn+1 = ¡9xn ¡ 5yn:

Solve the system for xn and yn in terms of x0 and y0.

Solution. Combine the above equations into a single matrix equation

·

xn+1

yn+1

¸

=

·

7 4

¡9 ¡5

¸ ·

xn

yn

¸

;

or Xn+1 = AXn, where A =

·

7 4

¡9 ¡5

¸

and Xn =

·

xn

yn

¸

.

We see that

X1 = AX0

X2 = AX1 = A(AX0) = A2X0

...

Xn = AnX0:

(The truth of the equation Xn = AnX0 for n ¸ 1, strictly speaking

follows by mathematical induction; however for simple cases such as the

above, it is customary to omit the strict proof and supply instead a few

lines of motivation for the inductive statement.)

Hence the previous example gives

·

xn

yn

¸

= Xn =

·

1 + 6n 4n

¡9n 1 ¡ 6n

¸ ·

x0

y0

¸

=

·

(1 + 6n)x0 + (4n)y0

(¡9n)x0 + (1 ¡ 6n)y0

¸

;

and hence xn = (1+6n)x0+4ny0 and yn = (¡9n)x0+(1¡6n)y0, for n ¸ 1.

Навигация