Skip to main content

Solve third-order recurrence with n·4ⁿ

Short answer

Characteristic roots: 2 (double) and 3. Particular solution (16n-80)·4^n. Solving with given initial conditions yields a_n = (17 + 39n/2)·2^n + 61·3^n + (16n-80)·4^n.

Find all solutions of the recurrence relation aₙ = 7aₙ₋₁ − 16aₙ₋₂ + 12aₙ₋₃ + n·4ⁿ with initial condition a₀ = −2, a₁ = 0 and a₂ = 5.

aₙ = 7aₙ₋₁ − 16aₙ₋₂ + 12aₙ₋₃ + n·4ⁿ is linear, non-homogeneous, of order 3.

Step 1. Homogeneous part

r³ - 7r² + 16r - 12 = 0  ->  (r - 2)²(r - 3) = 0

Roots: r = 2 (double), r = 3. So aₙ⁽ʰ⁾ = (A + Bn)2ⁿ + C·3ⁿ.

Step 2. Particular solution

F(n) = n·4ⁿ. Since 4 is not a root, try aₙ⁽ᵖ⁾ = (pn + q)4ⁿ. Substitute and divide by 4ⁿ⁻³ (4³ = 64, 4² = 16, 4¹ = 4 appear as factors):

64(pn+q) = 112[p(n-1)+q] - 64[p(n-2)+q] + 12[p(n-3)+q] + 64n
coefficient of n:  64p = 112p - 64p + 12p + 64 = 60p + 64   ->  p = 16
constant:          64q = -112p + 128p - 36p + (112-64+12)q
                   64q = -20p + 60q                        ->  q = -5p = -80

aₙ⁽ᵖ⁾ = (16n − 80)4ⁿ.

Step 3. General solution

aₙ = (A + Bn)2ⁿ + C·3ⁿ + (16n − 80)4ⁿ

Step 4. Initial conditions

n = 0:  A + C - 80 = -2                      ->  A + C = 78
n = 1:  2(A+B) + 3C + (16-80)·4 = 0          ->  2A + 2B + 3C = 256
n = 2:  4(A+2B) + 9C + (32-80)·16 = 5        ->  4A + 8B + 9C = 773

From the first, A = 78 − C. The second gives 2B + C = 100. The third gives 8B + 5C = 461. Then 4(2B + C) = 400 gives 8B + 4C = 400, and subtracting: C = 61. Hence B = 39/2 and A = 17.

Answer: aₙ = (17 + 39n/2)·2ⁿ + 61·3ⁿ + (16n − 80)·4ⁿ

Check: a₀ = 17 + 61 − 80 = −2 ✓; a₁ = 2(36.5) + 183 − 256 = 0 ✓; a₂ = 4(56) + 549 − 768 = 5 ✓; a₃ = 203 (formula and recurrence agree; verified in Python up to n = 11).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 3 questions →