🗊Презентация Solving linear recurrence relations

Категория: Математика
Нажмите для полного просмотра!
Solving linear recurrence relations, слайд №1Solving linear recurrence relations, слайд №2Solving linear recurrence relations, слайд №3Solving linear recurrence relations, слайд №4Solving linear recurrence relations, слайд №5Solving linear recurrence relations, слайд №6Solving linear recurrence relations, слайд №7Solving linear recurrence relations, слайд №8Solving linear recurrence relations, слайд №9Solving linear recurrence relations, слайд №10Solving linear recurrence relations, слайд №11Solving linear recurrence relations, слайд №12Solving linear recurrence relations, слайд №13Solving linear recurrence relations, слайд №14Solving linear recurrence relations, слайд №15Solving linear recurrence relations, слайд №16Solving linear recurrence relations, слайд №17Solving linear recurrence relations, слайд №18Solving linear recurrence relations, слайд №19Solving linear recurrence relations, слайд №20Solving linear recurrence relations, слайд №21Solving linear recurrence relations, слайд №22Solving linear recurrence relations, слайд №23Solving linear recurrence relations, слайд №24Solving linear recurrence relations, слайд №25Solving linear recurrence relations, слайд №26Solving linear recurrence relations, слайд №27Solving linear recurrence relations, слайд №28Solving linear recurrence relations, слайд №29Solving linear recurrence relations, слайд №30Solving linear recurrence relations, слайд №31Solving linear recurrence relations, слайд №32Solving linear recurrence relations, слайд №33Solving linear recurrence relations, слайд №34Solving linear recurrence relations, слайд №35Solving linear recurrence relations, слайд №36Solving linear recurrence relations, слайд №37Solving linear recurrence relations, слайд №38Solving linear recurrence relations, слайд №39Solving linear recurrence relations, слайд №40Solving linear recurrence relations, слайд №41Solving linear recurrence relations, слайд №42Solving linear recurrence relations, слайд №43Solving linear recurrence relations, слайд №44Solving linear recurrence relations, слайд №45Solving linear recurrence relations, слайд №46Solving linear recurrence relations, слайд №47Solving linear recurrence relations, слайд №48Solving linear recurrence relations, слайд №49Solving linear recurrence relations, слайд №50Solving linear recurrence relations, слайд №51Solving linear recurrence relations, слайд №52Solving linear recurrence relations, слайд №53Solving linear recurrence relations, слайд №54Solving linear recurrence relations, слайд №55Solving linear recurrence relations, слайд №56Solving linear recurrence relations, слайд №57Solving linear recurrence relations, слайд №58Solving linear recurrence relations, слайд №59Solving linear recurrence relations, слайд №60Solving linear recurrence relations, слайд №61Solving linear recurrence relations, слайд №62Solving linear recurrence relations, слайд №63Solving linear recurrence relations, слайд №64Solving linear recurrence relations, слайд №65Solving linear recurrence relations, слайд №66Solving linear recurrence relations, слайд №67Solving linear recurrence relations, слайд №68Solving linear recurrence relations, слайд №69

Содержание

Вы можете ознакомиться и скачать презентацию на тему Solving linear recurrence relations. Доклад-сообщение содержит 69 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации


Слайд 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
Описание слайда:
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 .
Описание слайда:
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:
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
  .

Описание слайда:
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.
Описание слайда:
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
Описание слайда:
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 :
Описание слайда:
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
Описание слайда:
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 .
Описание слайда:
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, .
Описание слайда:
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

 
Описание слайда:
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,
Описание слайда:
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

 
Описание слайда:
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.
Описание слайда:
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,
Описание слайда:
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

 
Описание слайда:
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.
Описание слайда:
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,
Описание слайда:
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

.
Описание слайда:
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.
Описание слайда:
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
.
Описание слайда:
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 
.
Описание слайда:
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 
.
Описание слайда:
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 
.
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
.
Описание слайда:
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,
Описание слайда:
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
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
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  .
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
Generating functions Example 17 The generating function for the sequence is

Слайд 49





Generating functions
Example 18
The generating function for the sequence  
is
Описание слайда:
Generating functions Example 18 The generating function for the sequence is

Слайд 50





Generating functions
Example 19
The generating function for the sequence 
is
Описание слайда:
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,
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
Solution of example 24 Let be the generating function for the sequence , that is, First note that

Слайд 58





 
Solution of example 24
Описание слайда:
Solution of example 24

Слайд 59





 
Solution of example 24
Описание слайда:
Solution of example 24

Слайд 60





 
Solution of example 24
Описание слайда:
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 .
Описание слайда:
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.)
Описание слайда:
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
Описание слайда:
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
Описание слайда:
Solution of example 25 We sum both sides of the last equation starting with , to find that

Слайд 65





 
Solution of example 25
Описание слайда:
Solution of example 25

Слайд 66





 
Solution of example 25
Описание слайда:
Solution of example 25

Слайд 67





 
Solution of example 25

Expanding the right-hand side of this equation into partial fractions gives
Описание слайда:
Solution of example 25  Expanding the right-hand side of this equation into partial fractions gives

Слайд 68





 
Solution of example 25
Описание слайда:
Solution of example 25

Слайд 69





 
Solution of example 25

Описание слайда:
Solution of example 25 



Похожие презентации
Mypresentation.ru
Загрузить презентацию