Презентация Solving linear recurrence relations онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Solving linear recurrence relations абсолютно бесплатно. Урок-презентация на эту тему содержит всего 69 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:69 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:4.38 MB
- Просмотров:84
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Solving linear recurrence relations Irina Prosvirnina
Linear homogeneous recurrence relations
with 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 1
A 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 1
The recurrence relation
is a linear homogeneous recurrence relation of degree
one.
№5 слайд
Содержание слайда: Linear homogeneous recurrence relations
with constant coefficients
Example 2
The 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 3
The recurrence relation
is a linear homogeneous recurrence relation of degree five.
№7 слайд
Содержание слайда: Linear homogeneous recurrence relations
with constant coefficients
Example 4
The recurrence relation
is not linear.
№8 слайд
Содержание слайда: Linear homogeneous recurrence relations
with constant coefficients
Example 5
The recurrence relation
is not homogeneous.
№9 слайд
Содержание слайда: Linear homogeneous recurrence relations
with constant coefficients
Example 6
The recurrence relation
does not have constant coefficients.
№10 слайд
Содержание слайда: Solving linear homogeneous recurrence relations
with constant coefficients
The basic approach for solving linear homogeneous recurrence relations
is to look for solutions of the form
where is a constant.
№11 слайд
Содержание слайда: Solving linear homogeneous recurrence relations
with constant coefficients
Note that
is 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 to give an explicit formula for all the solutions of the recurrence relation.
№15 слайд
Содержание слайда: Solving linear homogeneous recurrence relations with constant coefficients of degree two
Theorem 1
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 the sequence with is a solution of the recurrence relation
.
№17 слайд
Содержание слайда: Proof of theorem 1
? If the sequence is a solution of , then for , for some constants 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 some constants 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 some constants 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 some constants 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 some constants 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 7
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, .
№23 слайд
Содержание слайда: Solving linear homogeneous recurrence relations with constant coefficients of degree two
Example 7
What 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
Theorem 2
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 9
What 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 9
What is the solution of the recurrence relation
with and ?
Solution
№29 слайд
Содержание слайда: Solving linear homogeneous recurrence relations with constant coefficients of degree three
Theorem 3
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 10
What 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
Example 10
What is the solution of the recurrence relation
with
Solution
.
№32 слайд
Содержание слайда: Linear nonhomogeneous recurrence relations
with constant coefficients
Definition 2
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 11
The 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 12
The 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 13
The 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 14
The 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
Theorem 4
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
Because is 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 15
Find 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 15
Find 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 15
Find all solutions of the recurrence relation
Solution
№44 слайд
Содержание слайда: Linear nonhomogeneous recurrence relations
with constant coefficients
Example 16
Find 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 16
Find 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 16
Find all solutions of the recurrence relation
Solution
№47 слайд
Содержание слайда: Generating functions
Definition 3
The generating function for the sequence
of real numbers is the infinite series
№48 слайд
Содержание слайда: Generating functions
Example 17
The generating function for the sequence
is
№49 слайд
Содержание слайда: Generating functions
Example 18
The generating function for the sequence
is
№50 слайд
Содержание слайда: Generating functions
Example 19
The 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 20
The generating function of
is
We have
when .
Consequently, is the generating function of the sequence
№53 слайд
Содержание слайда: Generating functions
Example 21
Let be a positive integer.
The generating function for the sequence
with
is
The binomial theorem shows that
№54 слайд
Содержание слайда: Generating functions
Example 22
The function
is the generating function of the sequence
because
for
№55 слайд
Содержание слайда: Generating functions
Example 23
The function
is the generating function of the sequence
because
for
№56 слайд
Содержание слайда: Using generating functions to solve recurrence relations
Example 24
Solve the recurrence relation
for
and initial condition
№57 слайд
Содержание слайда: Solution of example 24
Let be the generating function for the sequence , that is,
First note that
№58 слайд
Содержание слайда: Solution of example 24
№59 слайд
Содержание слайда: Solution of example 24
№60 слайд
Содержание слайда: Solution of example 24
№61 слайд
Содержание слайда: Using generating functions to solve recurrence relations
Example 25
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 слайд
Содержание слайда: Solution of example 25
To 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 слайд
Содержание слайда: Solution of example 25
Let
be the generating function of the sequence
№64 слайд
Содержание слайда: Solution of example 25
We sum both sides of the last equation starting with , to find that
№65 слайд
Содержание слайда: Solution of example 25
№66 слайд
Содержание слайда: Solution of example 25
№67 слайд
Содержание слайда: Solution of example 25
Expanding the right-hand side of this equation into partial fractions gives
№68 слайд
Содержание слайда: Solution of example 25
№69 слайд
Содержание слайда: Solution of example 25
Скачать все slide презентации Solving linear recurrence relations одним архивом:
