Unit-05
Recurrence Relation:
Definition
Examples (Fibonacci,
Factorial etc.),
Linear recurrence
relations with constants coefficients –
Homogenous solutions
Particular solutions
Total solutions
Problems.
Homogenous solutions -
1. A linear recurrence relation with constant coefficients has a homogenous solution that depends only on the coefficients and the order of the relation.
2. The homogenous solution represents the general form of the sequence that satisfies the recurrence relation without considering the initial conditions.
3. The homogenous solution can be found by assuming that the terms of the sequence have a geometric form of the following form:
a(n) = r^n
where r is a constant to be determined.
a. Substituting this form into the recurrence relation gives:
r^n = c1r^(n-1) + c2r^(n-2) + ... + ck*r^(n-k)
b. Dividing both sides by r^(n-k) and rearranging, we obtain the characteristic equation:
r^k - c1r^(k-1) - c2r^(k-2) - ... - ck = 0
This equation is called the characteristic equation of the recurrence relation, and its roots determine the homogenous solution.
4. If the roots of the characteristic equation are distinct, then the homogenous solution has the following form:
a(n) = A1r1^n + A2r2^n + ... + Ak*rk^n
where r1, r2, ..., rk are the roots of the characteristic equation, and A1, A2, ..., Ak are constants to be determined using the initial conditions of the sequence.
5. If the roots are not distinct, then the homogenous solution has additional terms that depend on the multiplicity of the roots. For example, consider the linear recurrence relation:
a(n) = 4a(n-1) - 4a(n-2) + a(n-3)
The characteristic equation is:
r^3 - 4r^2 + 4r - 1 = 0 which has roots 1, 1, and -1. Therefore, the homogenous solution is:
a(n) = A11^n + A21^n + A3*(-1)^n
which simplifies to:
a(n) = A1 + A2 + (-1)^n*A3
The constants A1, A2, and A3 can be determined using the initial conditions of the sequence.
Particular solutions -
1. In addition to the homogenous solution, a linear recurrence relation with constant coefficients may also have a particular solution that depends on the specific values of the coefficients and the initial conditions.
2. The particular solution represents a particular sequence that satisfies the recurrence relation and the initial conditions.
3. The general solution of the recurrence relation is the sum of the homogenous solution and the particular solution.
4. To find the particular solution, one can use the method of undetermined coefficients, which involves assuming a form for the particular solution based on the form of the non-homogenous term of the recurrence relation.
5. The form of the particular solution depends on the type of non-homogenous term.
6. For example, consider the linear recurrence relation:
a(n) = 3a(n-1) - 2a(n-2) + 2^n
The homogenous solution of this recurrence relation is given by:
a(n) = A*2^n + B
where A and B are constants determined by the initial conditions.
7. To find the particular solution, we assume that it has the form:
a(n) = C*2^n
where C is a constant to be determined.
8. Substituting this form into the recurrence relation, we obtain:
C2^n = 3C2^(n-1) - 2C*2^(n-2) + 2^n
Simplifying and dividing by 2^n, we obtain: C = 2 Therefore, the particular solution is:
a(n) = 2*2^n
The general solution is the sum of the homogenous solution and the particular solution:
a(n) = A2^n + B + 22^n
where A and B are constants determined by the initial conditions.
No comments:
Post a Comment
Please do not enter any spam link in the comment box and use English and Hindi language for comment.