Similar presentations:

# Solving linear recurrence relations

## 1. Solving linear recurrence relations Irina Prosvirnina

• Linear homogeneous recurrence relationswith constant coefficients

• Solving linear homogeneous recurrence relations

with constant coefficients

• Solving linear homogeneous recurrence relations with

constant coefficients of degree two and of degree three

• Linear nonhomogeneous recurrence relations

with constant coefficients

• Generating functions

• Using generating functions to solve recurrence

relations

## 2. Linear homogeneous recurrence relations with constant coefficients

•Definition 1A linear homogeneous recurrence relation of degree

with constant coefficients is a recurrence relation of

the form

where are real numbers, and .

## 3. Linear homogeneous recurrence relations with constant coefficients

A sequence satisfying the recurrence relation in the

definition is uniquely determined by this recurrence

relation and the initial conditions:

## 4. Linear homogeneous recurrence relations with constant coefficients

•Example 1The recurrence relation

is a linear homogeneous recurrence relation of degree

one.

## 5. Linear homogeneous recurrence relations with constant coefficients

•Example 2The recurrence relation

is a linear homogeneous recurrence relation of degree

two.

The sequence of Fibonacci numbers satisfies this

recurrence relation and also satisfies the initial

conditions .

## 6. Linear homogeneous recurrence relations with constant coefficients

•Example 3The recurrence relation

is a linear homogeneous recurrence relation of degree

five.

## 7. Linear homogeneous recurrence relations with constant coefficients

•Example 4The recurrence relation

is not linear.

## 8. Linear homogeneous recurrence relations with constant coefficients

•Example 5The recurrence relation

is not homogeneous.

## 9. Linear homogeneous recurrence relations with constant coefficients

•Example 6The recurrence relation

does not have constant coefficients.

## 10. Solving linear homogeneous recurrence relations with constant coefficients

•The basic approach for solving linear homogeneousrecurrence relations

is to look for solutions of the form

where is a constant.

## 11. Solving linear homogeneous recurrence relations with constant coefficients

•Note thatis a solution of the recurrence relation

if and only if

## 12. Solving linear homogeneous recurrence relations with constant coefficients

When both sides of this equation are divided by , we

obtain the equation

When the right-hand side is subtracted from the left we

obtain the equation

## 13. Solving linear homogeneous recurrence relations with constant coefficients

Consequently,the sequence with is a solution of linear

homogeneous recurrence relations

with constant coefficients

is a solution if and only if

is a solution of this last equation

We call this the characteristic equation of the recurrence

relation .

The solutions of this equation are called the

characteristic roots of the recurrence relation .

## 14. Solving linear homogeneous recurrence relations with constant coefficients

As we will see, these characteristic roots can be used togive an explicit formula for all the solutions of the

recurrence relation.

## 15. Solving linear homogeneous recurrence relations with constant coefficients of degree two

Theorem1

Let and be real numbers. Suppose that

has two distinct roots and .

Then the sequence is a solution of the recurrence

relation

if and only if for , where and are constants.

## 16. Proof of theorem 1

?• If and are roots of , and are constants then thesequence with is a solution of the recurrence relation

.

## 17. Proof of theorem 1

?• If the sequence is a solution of , then for , for someconstants and , where and are distinct roots of .

Let is a solution of the recurrence relation

and the initial conditions hold.

## 18. Proof of theorem 1

?• If the sequence is a solution of , then for , for someconstants and , where and are distinct roots of .

It will be shown that there are constants and such that

the sequence with satisfies these same initial

conditions

## 19. Proof of theorem 1

?• If the sequence is a solution of , then for , for someconstants and , where and are distinct roots of .

This requires that

We can solve these two equations for and :

## 20. Proof of theorem 1

?• If the sequence is a solution of , then for , for someconstants and , where and are distinct roots of .

Hence, with these values for

the sequence with ,

satisfies the two initial conditions

## 21. Proof of theorem 1

?• If the sequence is a solution of , then for , for someconstants and , where and are distinct roots of .

We know that and are both solutions of the recurrence

relation and both satisfy the initial conditions when

and .

Because there is a unique solution of a linear

homogeneous recurrence relation of degree two with

two initial conditions, it follows that the two solutions

are the same, that is, for .

## 22. Solving linear homogeneous recurrence relations with constant coefficients of degree two

•Example 7What is the solution of the recurrence relation

with and ?

Solution

The characteristic equation of the recurrence relation is

Its roots are

and .

By theorem 1, .

## 23. Solving linear homogeneous recurrence relations with constant coefficients of degree two

•Example 7What is the solution of the recurrence relation

with and ?

Solution

## 24. Solving linear homogeneous recurrence relations with constant coefficients of degree two

•Example 8 (Fibonacci numbers)What is the solution of the recurrence relation

with and ?

Solution

The characteristic equation of the recurrence relation is

Its roots are

and .

By theorem 1,

## 25. Solving linear homogeneous recurrence relations with constant coefficients of degree two

•Example 8 (Fibonacci numbers)What is the solution of the recurrence relation

with and ?

Solution

## 26. Solving linear homogeneous recurrence relations with constant coefficients of degree two

Theorem2

Let and be real numbers with . Suppose that

has only one root .

A sequence is a solution of the recurrence relation

if and only if for , where and are constants.

## 27. Solving linear homogeneous recurrence relations with constant coefficients of degree two

•Example 9What is the solution of the recurrence relation

with and ?

Solution

The characteristic equation of the recurrence relation is

Its root is

.

By theorem 2,

## 28. Solving linear homogeneous recurrence relations with constant coefficients of degree two

•Example 9What is the solution of the recurrence relation

with and ?

Solution

## 29. Solving linear homogeneous recurrence relations with constant coefficients of degree three

Theorem3

Let be real numbers.

Suppose that the characteristic equation

has distinct roots .

A sequence is a solution of the recurrence relation

if and only if

for , where are constants.

## 30. Solving linear homogeneous recurrence relations with constant coefficients of degree three

•Example 10What is the solution of the recurrence relation

with

Solution

The characteristic equation of the recurrence relation is

Its roots are

.

By theorem 3,

## 31. Solving linear homogeneous recurrence relations with constant coefficients of degree three

Example10

What is the solution of the recurrence relation

with

Solution

.

## 32. Linear nonhomogeneous recurrence relations with constant coefficients

Definition2

A linear nonhomogeneous recurrence relation with

constant coefficients is a recurrence relation of the

form

where are real numbers, is a function not identically

zero depending only on .

The recurrence relation

is called the associated homogeneous recurrence

relation.

It plays an important role in the solution of the

nonhomogeneous recurrence relation.

## 33. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 11The recurrence relation

is a linear nonhomogeneous recurrence relation with

constant coefficients.

The associated linear homogeneous recurrence relation

is

.

## 34. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 12The recurrence relation

is a linear nonhomogeneous recurrence relation with

constant coefficients.

The associated linear homogeneous recurrence relation

is

.

## 35. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 13The recurrence relation

is a linear nonhomogeneous recurrence relation with

constant coefficients.

The associated linear homogeneous recurrence relation

is

.

## 36. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 14The recurrence relation

is a linear nonhomogeneous recurrence relation with

constant coefficients.

The associated linear homogeneous recurrence relation

is

.

## 37. Linear nonhomogeneous recurrence relations with constant coefficients

Theorem4

If is a particular solution of the nonhomogeneous

linear recurrence relation with

constant coefficients

,

then every solution is of the form ,

where is a solution of the associated

homogeneous recurrence relation

## 38. Proof of theorem 4

Becauseis a particular solution of the

nonhomogeneous recurrence relation

,

we know that

## 39. Proof of theorem 4

Now• suppose that is a second solution of the

nonhomogeneous recurrence relation

,

so that

.

## 40. Proof of theorem 4

So,,

.

Subtracting the first of these two equations from the

second shows that

It follows that is a solution of the associated homogeneous

linear recurrence relation,say,

Consequently,

## 41. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 15Find all solutions of the recurrence relation

Solution

This is a linear nonhomogeneous recurrence relation.

The solutions of its associated homogeneous

recurrence relation

are

## 42. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 15Find all solutions of the recurrence relation

Solution

We now find a particular solution.

Suppose that where and are constants, such a

solution.

## 43. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 15Find all solutions of the recurrence relation

Solution

## 44. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 16Find all solutions of the recurrence relation

Solution

This is a linear nonhomogeneous recurrence relation.

The solutions of its associated homogeneous

recurrence relation

are .

## 45. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 16Find all solutions of the recurrence relation

Solution

We now find a particular solution.

Suppose that is a

## 46. Linear nonhomogeneous recurrence relations with constant coefficients

•Example 16Find all solutions of the recurrence relation

Solution

## 47. Generating functions

•Definition 3The generating function for the sequence

of real numbers is the infinite series

## 48. Generating functions

•Example 17The generating function for the sequence

is

## 49. Generating functions

•Example 18The generating function for the sequence

is

## 50. Generating functions

•Example 19The generating function for the sequence

is

## 51. Generating functions

We• can define generating functions for finite sequences

of real numbers by extending a finite sequence

into an infinite sequence by setting

and so on.

The generating function of this infinite sequence is a

polynomial of degree because no terms of the form

with occur, that is,

## 52. Generating functions

•Example 20The generating function of

is

We have

when .

Consequently, is the generating function of the sequence

## 53. Generating functions

•Example 21Let be a positive integer.

The generating function for the sequence

with

is

The binomial theorem shows that

## 54. Generating functions

•Example 22The function

is the generating function of the sequence

because

for

## 55. Generating functions

•Example 23The function

is the generating function of the sequence

because

for

## 56. Using generating functions to solve recurrence relations

•Example 24Solve the recurrence relation

for

and initial condition

## 57. a_k=3a_(k-1), a_0=2

•Solution of example 24Let be the generating function for the sequence , that

is,

First note that

## 58. a_k=3a_(k-1), a_0=2

•Solution of example 24## 59. a_k=3a_(k-1), a_0=2

•Solution of example 24## 60. a_k=3a_(k-1), a_0=2

•Solution of example 24## 61. Using generating functions to solve recurrence relations

Example25

Solve the recurrence relation

for

and initial condition

Suppose that a valid codeword is an -digit number in

decimal notation containing an even number of 0s.

Let denote the number of valid codewords of length .

Proof that satisfies the recurrence relation

and the initial condition

Use generating functions to find an explicit formula for .

## 62. a_n=8a_(n-1)+〖10〗^(n-1), a_1=9

•Solution of example 25To make our work with generating functions simpler,

we extend this sequence by setting and use the

recurrence relation, we have

which is consistent with our original initial condition.

(It also makes sense because there is one code word of

length – the empty string.)

## 63. a_n=8a_(n-1)+〖10〗^(n-1), a_0=1

•Solution of example 25Let

be the generating function of the sequence

## 64. a_n=8a_(n-1)+〖10〗^(n-1), a_0=1

•Solution of example 25We sum both sides of the last equation starting with ,

to find that

## 65. a_n=8a_(n-1)+〖10〗^(n-1), a_0=1

•Solution of example 25## 66. a_n=8a_(n-1)+〖10〗^(n-1), a_0=1

•Solution of example 25## 67. a_n=8a_(n-1)+〖10〗^(n-1), a_0=1

•Solution of example 25Expanding the right-hand side of this equation into

partial fractions gives