Skip to main content

Solve aₙ=5aₙ₋₁−6aₙ₋₂+2ⁿ

Short answer

Homogeneous solution α·2^n + β·3^n; since 2 is a root of the characteristic equation, use particular solution -n·2^{n+1}. With a_0=1, a_1=4 gives α=-5, β=6. Thus a_n = -5·2^n + 6·3^n - n·2^{n+1}.

Find all the solutions of the recurrence relation: aₙ = 5aₙ₋₁ − 6aₙ₋₂ + 2ⁿ with initial conditions a₀ = 1 and a₁ = 4.

aₙ = 5aₙ₋₁ − 6aₙ₋₂ + 2ⁿ is linear, non-homogeneous, of order 2.

Step 1. Homogeneous part

r² − 5r + 6 = 0 gives r = 2, 3, so aₙ⁽ʰ⁾ = α·2ⁿ + β·3ⁿ.

Step 2. Particular solution

F(n) = 2ⁿ, and 2 is a (simple) root of the characteristic equation, so the usual guess c·2ⁿ fails; try aₙ⁽ᵖ⁾ = c·n·2ⁿ.

c n 2ⁿ = 5c(n-1)2ⁿ⁻¹ - 6c(n-2)2ⁿ⁻² + 2ⁿ          (divide by 2ⁿ⁻²)
4cn    = 10c(n-1) - 6c(n-2) + 4
4cn    = 4cn + 2c + 4
c = -2

aₙ⁽ᵖ⁾ = −2n·2ⁿ = −n·2ⁿ⁺¹.

Step 3. All solutions

aₙ = α·2ⁿ + β·3ⁿ − n·2ⁿ⁺¹

Step 4. Initial conditions

a₀ = 1:  α + β = 1
a₁ = 4:  2α + 3β - 4 = 4  ->  2α + 3β = 8

From the first, α = 1 − β; then 2 − 2β + 3β = 8 so β = 6 and α = −5.

Answer: aₙ = −5·2ⁿ + 6·3ⁿ − n·2ⁿ⁺¹

Check: a₂ = 5(4) − 6(1) + 4 = 18, formula: −20 + 54 − 16 = 18 ✓. a₃ = 5(18) − 24 + 8 = 74, formula: −40 + 162 − 48 = 74 ✓.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 3 questions →