--- title: "Solve third-order recurrence with n·4ⁿ" subject: "Discrete Structure" chapter: 3 key: "semester_4/discrete_structure:recurrence-third-order-n-4-power-n" source: https://www.bctengineer.com/q/semester_4/discrete_structure/recurrence-third-order-n-4-power-n site: BCT Engineering --- # Solve third-order recurrence with n·4ⁿ Discrete Structure · Chapter 3: Recurrence Relation - Asked in: 2069 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-third-order-n-4-power-n - Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-3 ## Question Find all solutions of the recurrence relation aₙ = 7aₙ₋₁ − 16aₙ₋₂ + 12aₙ₋₃ + n·4ⁿ with initial condition a₀ = −2, a₁ = 0 and a₂ = 5. ## 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. ## Answer aₙ = 7aₙ₋₁ − 16aₙ₋₂ + 12aₙ₋₃ + n·4ⁿ is linear, non-homogeneous, of order 3. #### Step 1. Homogeneous part ```text 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): ```text 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 ```text 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). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What factoring does r^3 − 7r^2 + 16r − 12 have? A. (r − 2)(r − 3)^2 B. (r − 1)(r − 3)(r − 4) C. (r + 2)^2(r + 3) D. (r − 2)^2 (r − 3) Answer: D. Roots 2 (double) and 3. (Key point: Homogeneous roots) 2. Which form follows? A. A·2^n + B·3^n B. (A + Bn)·2^n + C·3^n C. A·2^n + Bn·3^n D. (A + Bn)·3^n + C·2^n Answer: B. A double root gives the extra factor n. (Key point: Homogeneous solution) 3. Why is (pn + q)4^n used? A. 4 is a root B. F(n) is constant C. F(n) = n·4^n and 4 is not a root D. The order is 2 Answer: C. A polynomial of the same degree times 4^n. (Key point: Trial form) 4. What is p? A. −16 B. 60 C. 4 D. 16 Answer: D. 64p = 60p + 64 gives p = 16. (Key point: Value of p) ## Close variants set in other exams - [Solve aₙ=2aₙ₋₁+2n²](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-a-n-2a-2n-squared) — Discrete Structure, chapter 3, asked 6× - [Solve aₙ=3aₙ₋₁+2ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-a-n-3a-2n) — Discrete Structure, chapter 3, asked 6× - [Solve aₙ=2aₙ₋₁+2ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-a-n-2a-2n-a0-2) — Discrete Structure, chapter 3, asked 6× - [Solve aₙ=2aₙ₋₁+3ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-a-n-2a-3n) — Discrete Structure, chapter 3, asked 6× - [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× ## Related in Discrete Structure - [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× - [Set up recurrence for Tower of Hanoi](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-setup-recurrence) — Discrete Structure, chapter 3 - [Solve aₙ=5aₙ₋₁−6aₙ₋₂+3n+2ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-a-n-5a-6a-3n-2n) — Discrete Structure, chapter 3 - [Linear homogeneous and non-homogeneous recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alinear-homogeneous-nonhomogeneous-recurrence) — Discrete Structure, chapter 3 ## Related in other subjects - [Third order Bessel-Thomson constant delay filter](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Aconstant-delay-third-order-bessel) — Filter Design, chapter 2, asked 9× - [Triangulation principle; third-order specifications](https://www.bctengineer.com/question.md?key=semester_3%2Fsurveying_i%3Atriangulation-principle-third-order) — Surveying I, chapter 8 - [Third-order difference equation: limit x(k+2)/x(k+1)](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Athird-order-difference-limit-k1) — Digital Control System, chapter 2 - [Controllable canonical form of a third-order system](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Accf-1-3z-5z-4z) — Digital Control System, chapter 5, asked 14×