Skip to main content

Solve aₙ=2aₙ₋₁+2ⁿ

Short answer

Homogeneous part α·2^n. Since 2 is a root, particular solution is n·2^n. General solution (α+n)·2^n; a_0=2 gives α=2, so a_n = (n+2)·2^n.

Find all solutions of the recurrence relation aₙ = 2aₙ₋₁ + 2ⁿ with initial condition a₀ = 2.

aₙ = 2aₙ₋₁ + 2ⁿ is linear, non-homogeneous, of order 1.

Step 1. Homogeneous part

aₙ = 2aₙ₋₁ gives r = 2, so aₙ⁽ʰ⁾ = α·2ⁿ.

Step 2. Particular solution

F(n) = 2ⁿ and 2 is a root of the characteristic equation (multiplicity 1), so the guess c·2ⁿ would just duplicate the homogeneous solution. Use aₙ⁽ᵖ⁾ = c·n·2ⁿ.

c n 2ⁿ = 2c(n-1)2ⁿ⁻¹ + 2ⁿ
c n 2ⁿ = c(n-1)2ⁿ + 2ⁿ        (divide by 2ⁿ)
c n    = c n - c + 1
c = 1

aₙ⁽ᵖ⁾ = n·2ⁿ.

Step 3. All solutions

aₙ = α·2ⁿ + n·2ⁿ = (α + n)2ⁿ.

Step 4. Initial condition a₀ = 2

α = 2.

Answer: aₙ = (n + 2)·2ⁿ

Check: a₁ = 3·2 = 6 = 2(2) + 2 ✓; a₂ = 4·4 = 16 = 2(6) + 4 ✓; a₃ = 5·8 = 40 = 2(16) + 8 ✓.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 3 questions →