Find the general solution to each of the following recurrence relations. (a) an+2 —7a„+1 + 12a„ = 2" \ (b) an+2 Tan." + 12 a„= n2 (c) an+2 an+1 +12 a. = n2 24 (d) an+1 –2 a„ = cos n (e) an+2 an+1 +5...

1 answer below »
Find the general solution to each of the following recurrence relations. (a) an+2 —7a„+1 + 12a„ = 2" \ (b) an+2 Tan." + 12 a„= n2 (c) an+2 an+1 +12 a. = n2 24 (d) an+1 –2 a„ = cos n (e) an+2 an+1 +5 an = n. 2. To calculate the computational complexity — a measure for the maximal possible number of steps needed in a computation — of the `mergesore algorithm (an algorithm for sorting natural numbers into non-decreasing order) one can proceed by solving the following recurrence relation: a„ = 2 an_i + 2n — 1 , with ao = 0 . (a) Use the method of generating functions to solve this recurrence relation. (b) The relation between the number tm of computations needed to sort m numbers, and the solution am of the recurrence relation, is given by tr. = am . Use this to find an expression for t„ , where n = 2= (or loge n = m), explicitly as a function of n , and conclude that t„ ti n loge n for large n .



Document Preview:

Discrete Maths Homework






Discrete Maths Homework
Answered Same DayDec 22, 2021

Answer To: Find the general solution to each of the following recurrence relations. (a) an+2 —7a„+1 + 12a„ = 2"...

David answered on Dec 22 2021
128 Votes
Q 1.(a).
The given recurrence is
……………..(i)
The characteristic equation of (i) is x
2
-7x+12=0 => x=3 or 4
Homogenous solution of (i) is an= A13
n
+A24
n
For particular solution We assume that
an=A2
n
an+1=A2
n+1
an+2= A2
n+1
Now put this value in equation (i), we get
A2
n
- 7A2
n+1
+12A2
n+2
=2
n
 2n(A22-7A2+12A
-1)= 0
 4A-14A+12A-1=0
 A=1/2=0.5
The general solution of give equation is
an= A13
n
+A24
n
+(0.5 )2
n
Q 1.(b). The given recurrence is
……(i)
The characteristic equation of (i) is x
2
-7x+12=0 => x=3 or 4
Homogenous solution of (i) is an= A13
n
+A24
n
For particular solution We assume that
an=A0 + A1 n +A2n
2
an+1=A0 + A1 (n+1) +A2 (n+1)
2

an+2=A0 + A1 (n+2) +A2 (n+2)
2
Now put this value in equation (i), we get
A0 + A1 n +A2n
2
-7(A0 + A1 (n+1) +A2 (n+1)
2
) +12(A0 + A1 n +A2n
2
)=n
2
 6A0 +A1(6n-5)+A2(n
2
+4n+4-7(n
2
+2n+1)+12n
2
)=n
2

 6A0 +A1(6n-5)+A2(6n
2
-10n-3)=n
2

 6A0- 5A1-3A2=0 ………(ii)
And 6A1-10A2=0 …………(iii)
And 6A2=1 => A2 =1/6
Now put the value of A2 in equation (iii) ,we get ⁄

Now put the value of A2 and A1 in equation (ii)
( ) ⁄
= ⁄

The general solution of give equation is an= A13
n
+A24
n
+





Q 1.(c). The given recurrence is
……(i)
The characteristic equation of (i) is x
2
-7x+12=0 => x=3 or 4
Homogenous solution of (i) is an= A13
n
+A24
n
For particular solution We assume that
an=2
n
( A0 + A1 n +A2n
2
)
an+1=2
n+1
( A0 + A1 (n+1) +A2 (n+1)
2
)
an+2=2
n+2
( A0 + A1 (n+2) +A2 (n+2)
2
)
Now put this value in equation (i), we get
2
n+2
( A0 + A1 (n+2) +A2 (n+2)
2
) -7(2
n+1
( A0 + A1 (n+1) +A2 (n+1)
2
)) +12(2
n
(
A0 + A1 n +A2n
2
))=n
2
2
n

 A0(
-7 +12( )) +A1 (
( )-7 ( )+12( ) )
+A2((
( ) - 7( ( ) )+12( ) ) = n22n

 A0(
- +12( )) +A1(
( )-14 ( )+12( ) )
+A2((
( ) - 14( ( ) )+12( ) ) = n22n

 ( )
( )
( ) n
2
2
n

 2 =1 ⁄




=


The general solution of given recurrence is
an= A13
n
+A24
n
+ (



)
Q 1.(d). The given recurrence is …………………..(i)
For the given recurrence characteristic equation is x-2=0 =>x=2
the homogenous solution of given recurrence is an=A2
n
For particular solution we assume that
( ) ( )
Now put this value in equation (i)
( ) ( ) ( )
( ) ( )
( )
( ) (
)
Now equating the coefficient of both side we get the following equation
…………(a)
( ) ………(b)
From equation (b)



Put the value of A2 in equation (a), we get






The general solution of given recurrence is



Q 1. (e)
The given recurrence is ……….(i)
The characteristic equation of given recurrence is

the homogenous solution of given recurrence is
For particular solution We assume that
an=n( A + B n ) where A and B are constants
an+1=n+1( A + B (n+1) )
an+2=n+2( A + B (n+2))
now put this values in equation (i) we will get the...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here