Recurrence Relations
A recurrence relation defines a sequence in terms of its previous terms. Such relations occur frequently in mathematics, computer science, and discrete structures.
| Step | Rule |
| 1 | Write the characteristic equation for the given recurrence relation. |
| 2 | Solve the characteristic equation and find all roots. |
| 3 | The order of the recurrence = highest index − lowest index. |
| Nature of Roots | Complementary Solution an(h) |
| Real and distinct λ₁ ≠ λ₂ ≠ … ≠ λₖ |
an = C₁λ₁n + C₂λ₂n + … + Cₖλₖn |
| Real and equal λ₁ = λ₂ = … = λₖ |
an = (C₁ + C₂n + C₃n² + …) λ₁n |
| Complex conjugate roots λ = α ± iβ |
an = rn[ C₁ cos(nθ) + C₂ sin(nθ) ] where r = √(α² + β²), θ = tan−1(β/α) |
| f(n) | Assumed Particular Solution an(p) |
| Constant (C) | P₀ |
| Polynomial a + bn + cn² + … |
P₀ + P₁n + P₂n² + … |
| a·bn , b ≠ λ | P₀·bn |
| a·bn, b = λ (with multiplicity m) | P₀·nmbn |
| Total Solution |
| an = an(h) + an(p) |
Homogeneous Recurrence Relations
Example 1
Solve: an = an−1 + an−2, a0 = 0, a1 = 1
Characteristic equation for given equation
r2 = r + 1 ⇒ r2 − r − 1 = 0
Roots: r = (1 ± √5)/2
General solution: an = A( (1+√5)/2 )n + B( (1−√5)/2 )n
Using initial conditions:
a0 = A + B = 0 a1 = Aα + Bβ = 1
Solving, we get:
an = (1/√5)[ αn − βn ]
Example 2
Solve: an = 2an−1 + 3an−2, a0 = 1, a1 = 2
Characteristic equation:
r2 − 2r − 3 = 0 ⇒ (r − 3)(r + 1) = 0
Roots: r = 3, −1
an = A·3n + B(−1)n
Using initial conditions:
A + B = 1 3A − B = 2
Solving: A = 3/4, B = 1/4
an = (3/4)·3n + (1/4)(−1)n
Example 3
Given:
an = an−1 + an−2,
a0 = 0, a1 = 1
Step 1: Characteristic equation for given equation
r2 = r + 1
⇒ r2 − r − 1 = 0
Step 2: Solve the Characteristic Equation
Using the quadratic formula:
r = (1 ± √5) / 2
Let α = (1 + √5)/2 and β = (1 − √5)/2.
Step 3: General Solution
Since the roots are real and distinct, the general solution is:
an = Aαn + Bβn
Step 4: Apply Initial Conditions
Using a0 = 0:
A + B = 0
Using a1 = 1:
Aα + Bβ = 1
Solving these equations:
A = 1/√5, B = −1/√5
Final Solution
an = (1/√5)(αn − βn)
where α = (1 + √5)/2 and β = (1 − √5)/2.
Example 4
Solve: an = 11an−1 − 39an−2 + 45an−3, a0 = 5, a1 = 11, a2 = 25
Characteristic equation:
r3 − 11r2 + 39r − 45 = 0
Factoring,
(r − 3)2(r − 5) = 0
Roots are: r = 3 (repeated), r = 5
General solution:
an = (A + Bn)3n + C·5n
Using initial conditions:
a0 = A + C = 5
a1 = (A + B)3 + 5C = 11
a2 = (A + 2B)9 + 25C = 25
Solving, we get:
A = 4, B = −2, C = 1
Final solution:
an = (4 − 2n)3n + 5n
Example 5
Solve: Fn = Fn−1 + Fn−2, F0 = F1 = 1
Characteristic equation: r2 − r − 1 = 0
Solution:
Fn = Aαn + Bβn
Applying initial conditions gives the closed-form Fibonacci formula.
Example 6
Solve the recurrence relation:
Sn − 8Sn−1 − 12Sn−2 = 0, n ≥ 2
with initial conditions:
S0 = 54, S1 = 308
Solution:
Assume a solution of the form
Sn = rn
Substituting into the recurrence relation, we get
r2 − 8r − 12 = 0
This is the characteristic equation.
Solving,
r = (8 ± √112) / 2 = 4 ± 2√7
Hence, the general solution is
Sn = A(4 + 2√7)n + B(4 − 2√7)n
Using the initial conditions:
For n = 0:
A + B = 54
For n = 1:
A(4 + 2√7) + B(4 − 2√7) = 308
Solving these equations, we obtain
A = ½ (54 + 46 / √7), B = ½ (54 − 46 / √7)
Therefore, the required solution is
Sn = ½ (54 + 46 / √7)(4 + 2√7)n + ½ (54 − 46 / √7)(4 − 2√7)n
Non-Homogeneous Recurrence Relations
Example 7
Solve: an − 3an−1 = 2, n ≥ 1, a0 = 1
Homogeneous part:
an − 3an−1 = 0 ⇒ an(h) = A·3n
Particular solution (constant RHS): Assume an(p) = C
C − 3C = 2 ⇒ C = −1
General solution:
an = A·3n − 1
Using a0 = 1:
A − 1 = 1 ⇒ A = 2
an = 2·3n − 1
Example 8
Solve: ar+2 − 5ar+1 + 6ar = 2, with initial conditions a0 = 1 and a1 = −1
Step 1: Solve the associated homogeneous recurrence relation.
ar+2 − 5ar+1 + 6ar = 0
Assume ar = λr. Then the characteristic equation is
λ2 − 5λ + 6 = 0
(λ − 2)(λ − 3) = 0
Hence, λ = 2, 3
The complementary solution is
ar(h) = C1·2r + C2·3r
Step 2: Find a particular solution.
Since the right-hand side is a constant, assume
ar(p) = A
Substitute into the recurrence relation:
A − 5A + 6A = 2 ⇒ 2A = 2 ⇒ A = 1
Thus, the particular solution is
ar(p) = 1
Step 3: Write the general solution.
ar = ar(h) + ar(p)
ar = C1·2r + C2·3r + 1
Step 4: Apply the initial conditions.
For r = 0:
C1 + C2 + 1 = 1 ⇒ C1 + C2 = 0 …(1)
For r = 1:
2C1 + 3C2 + 1 = −1 ⇒ 2C1 + 3C2 = −2 …(2)
Solving (1) and (2), we get
C1 = 2, C2 = −2
Final Solution:
ar = 2·2r − 2·3r + 1
Example 9
Given:
ar+2 − 5ar+1 + 6ar = 2,
a0 = 1, a1 = −1
Step 1: Complementary (Homogeneous) Solution
Consider the associated homogeneous recurrence relation:
ar+2 − 5ar+1 + 6ar = 0
Assume ar = rn. The characteristic equation is:
r2 − 5r + 6 = 0
⇒ (r − 2)(r − 3) = 0
⇒ r = 2, 3
Hence, the complementary solution is:
ar(h) = A·2r + B·3r
Step 2: Particular Solution
The right-hand side is a constant (2). Assume a particular solution of the form:
ar(p) = C
Substitute into the recurrence relation:
C − 5C + 6C = 2
⇒ 2C = 2 ⇒ C = 1
Thus, the particular solution is:
ar(p) = 1
Step 3: General Solution
The general solution is:
ar = A·2r + B·3r + 1
Step 4: Apply Initial Conditions
Using a0 = 1:
A + B + 1 = 1 ⇒ A + B = 0
Using a1 = −1:
2A + 3B + 1 = −1 ⇒ 2A + 3B = −2
Solving the system:
A = 2, B = −2
Final Solution
ar = 2·2r − 2·3r + 1
Example 10
Solve: Sn − 4Sn−1 + 3Sn−2 = 5n
Characteristic equation:
r2 − 4r + 3 = 0 ⇒ r = 1, 3
Complementary solution:
Sn(h) = A + B·3n
Particular solution:
Assume Sn(p) = C·5n
Substitute into the recurrence relation:
C·5n − 4C·5n−1 + 3C·5n−2 = 5n
⇒ C·5n−2(25 − 20 + 3) = 5n
⇒ 8C·5n−2 = 5n
⇒ 8C = 25 ⇒ C = 25/8
Final solution:
Sn = A + B·3n + (25/8)·5n
Example 11
Solve:
an + 5an−1 + 6an−2 = 3n2
Given the recurrence relation
an + 5an−1 + 6an−2 = 3n2
Complementary (Homogeneous) Solution
The associated homogeneous recurrence relation is
an + 5an−1 + 6an−2 = 0
Assume a solution of the form
an = rn
Then the characteristic equation is
r2 + 5r + 6 = 0
(r + 2)(r + 3) = 0
⇒ r = −2, −3
Hence, the complementary function is
an(h) = C1(−2)n + C2(−3)n
Step 2: Particular Solution
Since the right-hand side is a polynomial 3n2, assume
an(p) = An2 + Bn + C
Then
an−1 = A(n−1)2 + B(n−1) + C
an−2 = A(n−2)2 + B(n−2) + C
Expanding,
an−1 = An2 − 2An + A + Bn − B + C
an−2 = An2 − 4An + 4A + Bn − 2B + C
Multiply by coefficients:
5an−1 = 5An2 − 10An + 5A + 5Bn − 5B + 5C
6an−2 = 6An2 − 24An + 24A + 6Bn − 12B + 6C
Adding all terms:
an + 5an−1 + 6an−2
= 12An2 + (−34A + 12B)n + (29A − 17B + 12C)
Step 3: Compare Coefficients
Comparing with 3n2, we obtain
12A = 3 ⇒ A = 1/4
−34A + 12B = 0 ⇒ B = 17/24
29A − 17B + 12C = 0 ⇒ C = 115/288
Step 4: Particular Solution
an(p) = (1/4)n2 + (17/24)n + 115/288
Step 5: General Solution
an = C1(−2)n + C2(−3)n + (1/4)n2 + (17/24)n + 115/288
Example 12
Solve: an + 5an−1 + 6an−2 = 3n2
Step 1: Complementary (Homogeneous) Solution
Consider the homogeneous recurrence relation:
an + 5an−1 + 6an−2 = 0
Assume an = rn. The characteristic equation is:
r2 + 5r + 6 = 0
⇒ (r + 2)(r + 3) = 0
⇒ r = −2, −3
Therefore, the complementary solution is:
an(h) = C1(−2)n + C2(−3)n
Step 2: Particular Solution
The right-hand side is a polynomial of degree 2, i.e. 3n2.
Assume a particular solution of the form:
an(p) = An2 + Bn + C
Substitute an, an−1, and an−2 into the given recurrence relation and compare coefficients of like powers of n.
Solving the resulting system of equations, we get:
A = 1/4, B = 19/24, C = 91/288
Thus, the particular solution is:
an(p) = (1/4)n2 + (19/24)n + 91/288
Step 3: General Solution
The general solution is the sum of the complementary and particular solutions:
an = C1(−2)n + C2(−3)n + (1/4)n2 + (19/24)n + 91/288
Example 13
Given: an − 4an−1 + 4an−2 = n + 3n
Step 1: Complementary (Homogeneous) Solution
Consider the associated homogeneous recurrence relation:
an − 4an−1 + 4an−2 = 0
Assume an = rn. The characteristic equation is:
r2 − 4r + 4 = 0
⇒ (r − 2)2 = 0
⇒ r = 2 (repeated root)
Therefore, the complementary solution is:
an(h) = (C1 + C2n)2n
Step 2: Particular Solution
The right-hand side is the sum of a polynomial term n and an exponential term 3n.
Assume a particular solution of the form:
an(p) = An + B + C·3n
Substitute this into the given recurrence relation and compare coefficients.
On solving, we obtain:
A = 1, B = 4, C = 9
Thus, the particular solution is:
an(p) = n + 4 + 9·3n
Step 3: General Solution
The general solution is the sum of the complementary and particular solutions:
an = (C1 + C2n)2n + n + 4 + 9·3n
Example 14
Solve: ar+2 − 5ar+1 + 6ar = 2 a0 = 1, a1 = −1
Characteristic equation: (r − 2)(r − 3) = 0
Particular solution: constant
ar = A·2r + B·3r − 1
Example 9
Solve: ar+2 + 2ar+1 − 3ar = 4
Characteristic equation: r2 + 2r − 3 = 0 ⇒ r = 1, −3
Particular solution: constant
ar = A·1r + B(−3)r − 2
Comments
Post a Comment