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
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)
are as follows −
