## 3/20/23

### Linear Recurrence Relation

Linear Recurrence Relation Part-02

Unit-05

Recurrence Relation: Definition

Examples (Fibonacci, Factorial etc.),

Linear recurrence relations with constants coefficients –

Homogenous solutions

Particular solutions

Total solutions

Problems.

Linear recurrence relations with constants coefficients

1.    A linear recurrence relation is a type of recurrence relation in which each term of a sequence is a linear combination of the previous k terms, where k is a fixed positive integer.

2.    The general form of a linear recurrence relation of order k is:

a(n) = c1a(n-1) + c2a(n-2) + ... + ck*a(n-k)

where c1, c2, ..., ck are constants and a(0), a(1), ..., a(k-1) are the initial terms of the sequence.

3.    For example, the Fibonacci sequence is a linear recurrence relation of order 2, where k=2 and the recurrence relation is:

F(n) = F(n-1) + F(n-2) where F(0) = 0 and F(1) = 1.

4.    Another example is the sequence of triangular numbers, which is a linear recurrence relation of order 2, where k=2 and the recurrence relation is:

T(n) = T(n-1) + n where T(1) = 1.

Linear recurrence relations can be solved using a variety of techniques, such as finding the characteristic equation, using generating functions, or using matrix methods.

The solution to a linear recurrence relation is a closed-form expression that gives the value of the nth term of the sequence in terms of the initial conditions and the coefficients of the recurrence relation.

To solve a linear recurrence relation with constant coefficients, one can use the following steps:

1.              Find the characteristic equation by replacing a(n) with x^n in the recurrence relation, giving:

x^k - c1x^(k-1) - c2x^(k-2) - ... - ck = 0

2.              Solve the characteristic equation to find its roots. If the roots are distinct, then the general solution to the recurrence relation is:

a(n) = Ar1^n + Br2^n + ... + Z*rk^n

where r1, r2, ..., rk are the roots of the characteristic equation, and A, B, ..., Z are constants determined by the initial conditions.

If the roots are not distinct, then the general solution involves additional terms that depend on the multiplicity of the roots.

3.      Use the initial conditions to determine the values of the constants A, B, ..., Z in the general solution.

4.      Write the final solution as a closed-form expression that gives the value of a(n) in terms of the initial conditions and the coefficients c1, c2, ..., ck of the recurrence relation.

For example,

The Fibonacci sequence is a linear recurrence relation with constant coefficients, where k=2 and the coefficients are c1=1 and c2=1.

The characteristic equation is:

x^2 - x - 1 = 0

which has roots:

r1 = (1 + sqrt(5))/2 r2 = (1 - sqrt(5))/2

The general solution to the recurrence relation is:

F(n) = Ar1^n + Br2^n

where A and B are constants determined by the initial conditions F(0) = 0 and F(1) = 1.

The final solution is:

F(n) = (1/sqrt(5)) * [(r1^n - r2^n)]

which gives the nth term of the Fibonacci sequence.

### Part 01 Recurrence Relation- Click mePart 02 Linear Recurrence Relation- Click mePart 03 Homogeneous and Particular Solutions- Click mePart 04 Total solutions and problem- Click me 