Question

Fn+5Fn-1 + 6Fn-2= 3n2- 2n+1 recurrence relaton solution

Answer 1

Answer:

Courses

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