## 3/20/23

### Total solutions and Problems

Total solutions and  Problems Part-04

Unit-05

Recurrence Relation: Definition

Examples (Fibonacci, Factorial etc.),

Linear recurrence relations with constants coefficients –

Homogenous solutions

Particular solutions

Total solutions

Problems.

Total solutions-

1.    The total solution of a linear recurrence relation with constant coefficients is the sum of the homogenous solution and the particular solution.

2.    The homogenous solution represents the general form of the sequence that satisfies the recurrence relation without considering the initial conditions, while the particular solution represents a particular sequence that satisfies both the recurrence relation and the initial conditions.

3.    To find the total solution, we first find the homogenous solution by solving the characteristic equation of the recurrence relation.

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 of the characteristic equation are not distinct, then the homogenous solution has additional terms that depend on the multiplicity of the roots.

6.    Next, we find the particular solution using the method of undetermined coefficients.

7.    The particular solution represents a particular sequence that satisfies both the recurrence relation and the initial conditions.

8.    Finally, the total solution is the sum of the homogenous solution and the particular solution.

9.    The constants in the homogenous solution are determined using the initial conditions, while the constant in the particular solution is determined by solving for it using the recurrence relation and the initial conditions.

10.         For example, consider the linear recurrence relation:

a(n) = 3a(n-1) - 2a(n-2) + 2^n

The characteristic equation of this recurrence relation is:

r^2 - 3r + 2 = 0

which has roots 1 and 2.

Therefore, the homogenous solution is:

a(n) = A11^n + A22^n

where A1 and A2 are constants to be determined using the initial conditions.

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. 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 total solution is the sum of the homogenous solution and the particular solution:

a(n) = A11^n + A22^n + 2*2^n

where A1 and A2 are constants determined by the initial conditions.

Problems-

1.              Find the 10th term of the sequence defined by the linear recurrence relation a(n) = 2a(n-1) + 3a(n-2) with initial conditions a(0) = 1 and a(1) = 2.

To solve this problem, we first find the characteristic equation of the recurrence relation:

r^2 - 2r - 3 = 0

which has roots r = -1 and r = 3.

Therefore, the homogenous solution is:

a(n) = A1*(-1)^n + A2*3^n

where A1 and A2 are constants determined by the initial conditions. Substituting the initial conditions, we obtain:

A1 + A2 = 1

A1 + 3*A2 = 2

Solving this system of equations, we obtain

A1 = 1 and A2 = 1/2.

Therefore, the total solution is:

a(n) = 1*(-1)^n + (1/2)*3^n

The 10th term of the sequence is:

a(10) = 1*(-1)^10 + (1/2)*3^10 = 5900.5

2.              Find the general form of the sequence defined by the linear recurrence relation a(n) = 4a(n-1) - 4a(n-2) + 2^n with initial conditions a(0) = 1 and a(1) = 3.

To solve this problem, we first find the characteristic equation of the recurrence relation:

r^2 - 4r + 4 = 0

which has a repeated root r = 2.

Therefore, the homogenous solution is:

a(n) = (A1 + A2*n)*2^n

where A1 and A2 are constants determined by the initial conditions.

Substituting the initial conditions, we obtain:

A1 = 1 A1 + 2*A2 = 3

Solving this system of equations, we obtain

A1 = 1 and A2 = 1/2.

Therefore, the general form of the sequence is:

a(n) = (1 + n/2)*2^n

3.              Find the particular solution of the linear recurrence relation a(n) = 3a(n-1) - 2a(n-2) + 2^n with initial conditions a(0) = 1 and a(1) = 2.

To solve this problem, we use the method of undetermined coefficients to find the particular solution.

We assume that the particular solution has the form:

a(n) = C*2^n

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 total solution is the sum of the homogenous solution and the particular solution, which we have already found in previous examples.

### 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 