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.
