power point DM Unit-4 part2 -21-04-2020.pptx

DM

1. Recurrence relations
Definition
A recurrence relation for the sequence
}{
n
a
is an
equation that express
na
in terms of one or more
of the previous terms of the sequence, namely ,
1210
,,,,


n
aaaa
for all integers
1n

2. Example
023.1
21

nnn
aaa

165.2
2
21


naaa
nnn

first one is homogeneous recurrence relation
second one is inhomogeneous recurrence relation

3. The Fibonacci Recurrence relation
Definition
The recurrence relation
2,
21
nFFF
nnn

with initial conditions
1
10
FF
is known as
Fibonacci Recurrence relation.

4. Solutions of recurrence relations
Definition
A sequence

0
}{
nn
a
is said to be a solution of
recurrence relation if each value
),,,,(
210

nn
aaaaa

satisfies the recurrence relation

5. Methods of solving recurrence relations
1.Substitution method
2. Generating functions
3. Characteristic roots

6. 1. Substitution method
Problem
Solve the recurrence
2
1
naa
nn



where a0 =7 by substitution method

7. Solution
Initial condition is a0 =7
we have a1 = a0 + 1
2
=7 + 1
2

a2 = a1 + 2
2
= 7 + 1
2
+ 2
2

a3 = a2 + 3
2
= 7 + 1
2
+ 2
2
+3
2

--------------------------------------
an = 7 + (1
2
+ 2
2
+3
2
+ --------+ n
2
)

 
6
121
7


nnn

which is the required solution.

8. Problem
If “an “ is a solution of an+1=kan for
0n

and
49
153
3a
and
2401
1377
5a

find the value of ‘k’ .

9. Solution
Given an+1=kan
put n=0
then a1 =k a0
put n=1
then a2= k a1
substituting the value of a1
we get a2= k( k a0)
a2= k
2
(a0)

10. similarly a3= k
3
(a0) ------(1)
a4= k
4
(a0)
a5= k
5
(a0) -------(2)
Given
49
153
3a
and
2401
1377
5a

substituting these in (1) and (2) we get
0
3
49
153
ak
---------(3)
0
5
2401
1377
ak
-----------(4)

11. 49
9
)3(
)4(
2
k

7
3
k

12. 2. Generating function method
Problem
Solve the recurrence an = 3an-1 for n=1,2,3---- and
initial condition a0 =2 using generating function
method

13. Solution
Given an - 3an-1 =0 -------(1)
for n=1,2,3---- and initial condition a0 =2
We multiply both sides of recurrence relation(1) by
n
x

then (1) becomes
03
1


n
n
n
n
xaxa
--------------(2)

14. summing both sides of the equation(2) starting with
n=1 we get
03
1
11







n
n
n
n
n
n
xaxa
-
which can be written as
03
1
1
11








n
n
n
n
n
n
xaxxa

that is
03
01





n
n
n
n
n
n
xaxxa
------------(3)

15. Let A(x) be the generating function for the sequence
{an} ,that is





0n
n
nxaxA
------------(4)




1
0
n
n
n
xaaxA
---------(5)
given a0 =2

)5(





1
2
n
n
n
xaxA






1
2
n
n
n
xaxA

16. that is
2
1



xAxa
n
n
n
-----------------(6)
From (3) ,(4) and (6) we get
 0)(32)(xAxxA

2)(3)(xAxxA

231xAx

Solving

x
xA
31
2



17. using the identity

n
n
n
xa
ax





01
1

we have





x
xA
31
2
n
n
n
x

0
32



n
n
n
x



0
32

 
n
n
a32

which is the required solution

18. Problem
Solve the recurrence relation for n=1,2,3----
1
1108


n
nnaa

with a0 =1, a1= 9, using generating function
method

19. Solution
the recurrence relation for n=1,2,3----
1
1108


n
nnaa
------------(1)
We multiply both sides of recurrence relation(1) by
n
x

then (1) becomes
nnn
n
n
nxxaxa
1
1108


---------------(2)

20. summing both sides of the equation(2) starting with
n=1 we get
 
nnn
n
n
n
n
n
xxaxa
1
1
11
108







------------(3)
Let A(x) be the generating function for the sequence
{an} ,that is





0n
n
n
xaxA
------------(4)




1
0
n
n
n
xaaxA
---------(5)

21. given a0 =1
)5(





1
1
n
n
n
xaxA






1
1
n
n
nxaxA

that is
1
1



xAxa
n
n
n
-----------------(6)

22. from(3) and (6)we get
1xA
 
nnn
n
n
xxa
1
1
1
108






taking constant “8” out side
1xA
n
n
nn
n
n
xxa







1
1
1
1
108

in R.H.S taking ‘‘x” out side
1xA
1
1
11
1
1
108








n
n
nn
n
n
xxxax

Which can be written as
1xA

n
n
nn
n
n
xxxax





00
108
-------(7)

23. from equation (4) and using the identity

n
n
n
xa
ax





01
1

(7) becomes
1xA
x
x
xAx
101
)(8



which gives








x
x
xxA
101
181)(

24. simplifying

 xx
x
xA
10181
91



---------------(8)
using partial fractions , R.H.S becomes
 x
B
x
A
xx
x
1018110181
91







solving we get A, B =1/2
(8) becomes
 









xx
xA
101
1
81
1
2
1
------(9)

25. again using the identity

n
n
n
xa
ax





01
1

(9) becomes
 









00
108
2
1
nn
nnnn
xxxA

  
nnn
n
xxA108
2
1
0



which gives the required solution
 
nn
na108
2
1


26. 3. Method Of Characteristics Roots
Definition
Let
0
,0
2211



k
knknnn
c
acacaca

---------(1)
be a linear homogeneous recurrence relation of
degree “k”. Then the equation
0
2
2
1
1


k
kkk
ctctct

--------(2)
is called the characteristic equation of the given
recurrence relation (1)

27. Degree of equation(2) is “k” , therefore it has
“k” roots.
Let
k
,,,
321
be the roots of the equation(2) and the roots
k
,,,
321
are called characteristic roots.

28. There are two cases
Case-1
If k
,,,
321 are distinct roots
then the general solution of the recurrence
relation is given by
n
kn
nn
n
ccca
2211
where k
ccc,,
21 are constants

29. Case-2
If the root  is repeated “k” times then the
general solution of the recurrence relation is
given by
 
nk
k
n
nDnDnDD
a

12
321




where D1 , D2 ,D3 , ---------,DK are constants.

30. Problem
Solve
2;023
21


naaa
nnn

31. Solution
The characteristic equation is
023
2
tt

which can be factorized as
021tt

2,1t

roots are different
The general solution is  
nn
n
cca21
21


32. Problem
Solve
096
21
nnnaaa

33. Solution
The characteristic equation is
023
2
tt

which can be written as
03
2
t
t =3,3
here roots are repeated
The general solution is
 
n
n
nDDa3
21


34. Problem
Solve
027279
321

nnnn
aaaa

35. Solution
The characteristic equation is
027279
23
ttt

which can be written03
3
t
t = 3 ,3,3
rootes are repeated three times
The general solution is
 
n
n
nDnDDa3
2
321


36. Problem
Find the characteristic polynomial , characteristic
equation for the homogeneous recurrence relation
whose general solution has the form
1)

21
BnBa
n


2)

nn
n
BBa32
21


37. Solution
1) Given general solution is 21
BnBa
n


That can be written as
 
nn
n
BnBa11
21


the characteristic polynomial is 
2
1t
 The characteristic equation is 01
2
t

38. 2)Given general solution is
nn
n
BBa32
21


the characteristic polynomial is
 6532
2
tttt
 The characteristic equation is
065
2
tt

39. Problem
Solve the Fibonacci relation
21

nnn
aaa

with
1,0
1
aa
o
as initial conditions.

40. Solution
We can rewrite the problem as
0
21

nnn
aaa

the characteristic equation is
01
2
tt

roots are finding using the formula
a
acbb
2
4
2


roots are
2
51
t

41. roots are different
the general solution is
nn
nCCa


















2
51
2
51
21

-----------------(1)

42. initial conditions are given as
1,0
1
aa
o
In equation (1) put n=0
then we get
0
2
0
10
2
51
2
51

















CCa

put
0
o
a

which gives
210CC -------------------(2)

43. In equation (1) put n=1
then we get
1
2
1
11
2
51
2
51

















CCa

put a1 = 1
which gives
1
2
1
1
2
51
2
51
1

















CC
------------(3)

44. solving (2) and (3) we get

,
5
1
1C 






5
1
2C

substituting this in equation (1) we get
nn
na


















2
51
5
1
2
51
5
1

This is the complete solution of the Fibonacci
relation .