---
title: "Solve aₙ=5aₙ₋₁−6aₙ₋₂+3n+2ⁿ"
subject: "Discrete Structure"
chapter: 3
key: "semester_4/discrete_structure:recurrence-a-n-5a-6a-3n-2n"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/recurrence-a-n-5a-6a-3n-2n
site: BCT Engineering
---

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

Discrete Structure · Chapter 3: Recurrence Relation

- Asked in: 2075 Bhadra, 8 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/recurrence-a-n-5a-6a-3n-2n
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-3

## Question

Find the solution of recurrence relation aₙ = 5aₙ₋₁ − 6aₙ₋₂ + 3n + 2ⁿ, with initial condition a₀ = 0, a₁ = 1, and a₂ = 2.

## Short answer

Homogeneous solution: α·2^n + β·3^n. Particular: (3/2)n + 21/4 - n·2^{n+1}. Using a0=0, a1=1 gives α=-14, β=35/4. So a_n = -14·2^n + (35/4)·3^n + (3/2)n + 21/4 - n·2^{n+1}.

## Answer

**Reading of the question:** the recurrence is of order 2, so two initial values a₀ = 0, a₁ = 1 determine the solution. The third value a₂ = 2 given in the question is not consistent with the relation (the recurrence gives a₂ = 5(1) − 6(0) + 6 + 4 = 15). So I use a₀ and a₁ and apply the relation for n ≥ 2.

#### Step 1. Homogeneous part
aₙ = 5aₙ₋₁ − 6aₙ₋₂ gives r² − 5r + 6 = 0, so r = 2, 3.
aₙ⁽ʰ⁾ = α·2ⁿ + β·3ⁿ.

#### Step 2. Particular solution
F(n) = 3n + 2ⁿ. Handle the two terms separately.

(a) For 3n (1 is not a root): try pn + q. Substituting:
```text
pn + q = 5[p(n-1)+q] - 6[p(n-2)+q] + 3n
pn + q = -pn + 7p - q + 3n
n:      p = -p + 3     ->  p = 3/2
const:  q = 7p - q     ->  q = 7p/2 = 21/4
```
(b) For 2ⁿ: 2 is a simple root of the characteristic equation, so try c·n·2ⁿ.
```text
c n 2ⁿ = 5c(n-1)2ⁿ⁻¹ - 6c(n-2)2ⁿ⁻² + 2ⁿ        (divide by 2ⁿ⁻²)
4cn = 10c(n-1) - 6c(n-2) + 4 = 4cn + 2c + 4
0 = 2c + 4   ->  c = -2
```
Particular solution: aₙ⁽ᵖ⁾ = (3/2)n + 21/4 − 2n·2ⁿ.

#### Step 3. General solution
aₙ = α·2ⁿ + β·3ⁿ + (3/2)n + 21/4 − n·2ⁿ⁺¹

#### Step 4. Use initial conditions
```text
n = 0:  α + β + 21/4 = 0                    ->  α + β = -21/4
n = 1:  2α + 3β + 3/2 + 21/4 - 4 = 1       ->  2α + 3β = -7/4
```
Subtracting 2×(first) from the second: β = −7/4 + 42/4 = 35/4, then α = −21/4 − 35/4 = −14.

**Answer: aₙ = −14·2ⁿ + (35/4)·3ⁿ + (3/2)n + 21/4 − n·2ⁿ⁺¹**

Check: this gives a₀ = 0, a₁ = 1, a₂ = 15, a₃ = 86, a₄ = 368, which agrees with the recurrence (verified in Python for n up to 11).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What are the roots of the homogeneous part a_n = 5a_(n-1) − 6a_(n-2)?
   A. r = 1 and r = 6
   B. r = −2 and r = −3
   C. r = 5 and r = 6
   D. r = 2 and r = 3
   Answer: D. r^2 − 5r + 6 = (r−2)(r−3). (Key point: Characteristic roots)

2. What trial form is used for the term 3n?
   A. pn + q, since 1 is not a root
   B. pn^2 + qn
   C. c·n·3^n
   D. c·3^n
   Answer: A. A linear polynomial is tried as 1 is not a characteristic root. (Key point: Guess for 3n)

3. Why is c·n·2^n used for 2^n?
   A. Because 2^n grows fastest
   B. Because 2 is a root of the characteristic equation
   C. Because 3 is a root
   D. Because it is a polynomial
   Answer: B. c·2^n would duplicate a homogeneous solution, so multiply by n. (Key point: Guess for 2^n)

4. Which initial values are used and why?
   A. All three, to find three constants
   B. Only a2
   C. a0 and a1, since the order is 2; a2 = 2 is inconsistent with the relation
   D. a1 and a2
   Answer: C. The recurrence gives a2 = 15, not 2. (Key point: Initial conditions)

## Related in Discrete Structure

- [Solve aₙ=5aₙ₋₁−6aₙ₋₂+2ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-5a-6a-2n-a0-1-a1-4) — Discrete Structure, chapter 3, asked 6×
- [Solve third-order recurrence with n·4ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-third-order-n-4-power-n) — Discrete Structure, chapter 3, asked 6×
- [Derive and solve Tower of Hanoi recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-derive-and-solve) — Discrete Structure, chapter 3
- [What is a recurrence relation](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-relation-definition) — Discrete Structure, chapter 3, asked 2×