Solve the recurrence relation − Fn=10Fn−1−25Fn−2 where F0=3 and F1=17
Answers
Answer:
Explanation:
Recurrence Relations
Recursive techniques can derive sequences and be used for solving counting problems. The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation. We study the theory of linear recurrence relations and their solutions. Finally, we introduce generating functions for solving recurrence relations.
Definition
A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing Fn as some combination of Fi with i<n ).
Example − Fibonacci series − Fn=Fn−1+Fn−2, Tower of Hanoi − Fn=2Fn−1+1
Linear Recurrence Relations
A linear recurrence equation of degree k or order k is a recurrence equation which is in the format xn=A1xn−1+A2xn−1+A3xn−1+…Akxn−k
(An is a constant and Ak≠0
) on a sequence of numbers as a first-degree polynomial.
These are some examples of linear recurrence equations −
How to solve linear recurrence relation
Suppose, a two ordered linear recurrence relation is − Fn=AFn−1+BFn−2
where A and B are real numbers.
The characteristic equation for the above recurrence relation is −
x2−Ax−B=0
Three cases may occur while finding the roots −
Case 1 − If this equation factors as (x−x1)(x−x1)=0 and it produces two distinct real roots x1 and x2, then Fn=axn1+bxn2 is the solution. [Here, a and b are constants]
Case 2 − If this equation factors as (x−x1)2=0 and it produces single real root x1, then Fn=axn1+bnxn1 is the solution.
Case 3 − If the equation produces two distinct complex roots, x1 and x2 in polar form x1=r∠θ and x2=r∠(−θ), then Fn=rn(acos(nθ)+bsin(nθ)) is the solution.
Problem 1
Solve the recurrence relation Fn=5Fn−1−6Fn−2 where F0=1 and F1=4
Solution
The characteristic equation of the recurrence relation is −
x2−5x+6=0,
So, (x−3)(x−2)=0
Hence, the roots are −
x1=3 and x2=2
The roots are real and distinct. So, this is in the form of case 1
Hence, the solution is −
Fn=axn1+bxn2
Here, Fn=a3n+b2n (As x1=3 and x2=2)
Therefore,
1=F0=a30+b20=a+b4=F1=a31+b21=3a+2b
Solving these two equations, we get a=2 and b=−1
Hence, the final solution is −
Fn=2.3n+(−1).2n=2.3n−2n
Problem 2
Solve the recurrence relation − Fn=10Fn−1−25Fn−2 where F0=3 and F1=17
Solution
The characteristic equation of the recurrence relation is −
x2−10x−25=0
So (x−5)2=0
Hence, there is single real root x1=5
As there is single real valued root, this is in the form of case 2
Hence, the solution is −
Fn=axn1+bnxn13=F0=a.50+b.0.50=a17=F1=a.51+b.1.51=5a+5b
Solving these two equations, we get a=3 and b=2/5
Hence, the final solution is − Fn=3.5n+(2/5).n.2n
Problem 3
Solve the recurrence relation Fn=2Fn−1−2Fn−2 where F0=1 and F1=3
Solution
The characteristic equation of the recurrence relation is −
x2−2x−2=0
Hence, the roots are −
x1=1+i and x2=1−i
In polar form, x1=r∠θ and x2=r∠(−θ), where r=2‾√ and θ=π4
The roots are imaginary. So, this is in the form of case 3.
Hence, the solution is −
Fn=(2‾√)n(acos(n.⊓/4)+bsin(n.⊓/4))1=F0=(2‾√)0(acos(0.⊓/4)+bsin(0.⊓/4))=a3=F1=(2‾√)1(acos(1.⊓/4)+bsin(1.⊓/4))=2‾√(a/2‾√+b/2‾√)
Solving these two equations we get a=1 and b=2
Hence, the final solution is − Fn=(2‾√)n(cos(n.π/4)+2sin(n.π/4))
Non-Homogeneous Recurrence Relation and Particular Solutions
A recurrence relation is called non-homogeneous if it is in the form Fn=AFn−1+BFn−2+f(n) where f(n)≠0
Its associated homogeneous recurrence relation is Fn=AFn–1+BFn−2
The solution (an) of a non-homogeneous recurrence relation has two parts.
First part is the solution (ah) of the associated homogeneous recurrence relation and the second part is the particular solution (at).
an=ah+at
Solution to the first part is done using the procedures discussed in the previous section.
To find the particular solution, we find an appropriate trial solution.
Let f(n)=cxn ; let x2=Ax+B be the characteristic equation of the associated homogeneous recurrence relation and let x1 and x2 be its roots.
If x≠x1 and x≠x2, then at=Axn
If x=x1 , x≠x2, then at=Anxn
If x=x1=x2, then at=An2xn
Example
Let a non-homogeneous recurrence relation be Fn=AFn–1+BFn−2+f(n)
with characteristic roots x1=2 and x2=5. Trial solutions for different possible values of f(n)