1. **Problem statement:** Compute the solution of the recurrence relation $$a_n = 4a_{n-1} - 3a_{n-2} + 2^n + n + 3$$ with initial conditions $$a_0 = 1$$ and $$a_1 = 4$$. 2. **Step 1: Solve the homogeneous recurrence relation** The associated homogeneous recurrence is: $$a_n^h = 4a_{n-1}^h - 3a_{n-2}^h$$ The characteristic equation is: $$r^2 - 4r + 3 = 0$$ Factoring: $$(r - 3)(r - 1) = 0$$ So the roots are $$r = 3$$ and $$r = 1$$. 3. **Step 2: General solution of the homogeneous part** $$a_n^h = A \cdot 3^n + B \cdot 1^n = A3^n + B$$ where $$A$$ and $$B$$ are constants to be determined. 4. **Step 3: Find a particular solution $$a_n^p$$** The nonhomogeneous part is: $$f(n) = 2^n + n + 3$$ We try a particular solution of the form: $$a_n^p = C \cdot 2^n + Dn + E$$ where $$C, D, E$$ are constants to be found. 5. **Step 4: Substitute $$a_n^p$$ into the recurrence** Calculate: $$a_n^p = C2^n + Dn + E$$ $$a_{n-1}^p = C2^{n-1} + D(n-1) + E$$ $$a_{n-2}^p = C2^{n-2} + D(n-2) + E$$ Substitute into the recurrence: $$C2^n + Dn + E = 4\left(C2^{n-1} + D(n-1) + E\right) - 3\left(C2^{n-2} + D(n-2) + E\right) + 2^n + n + 3$$ 6. **Step 5: Simplify terms involving $$2^n$$** Note that: $$4C2^{n-1} = 4C \cdot \frac{2^n}{2} = 2C2^n$$ $$-3C2^{n-2} = -3C \cdot \frac{2^n}{4} = -\frac{3C}{4}2^n$$ So the $$2^n$$ terms on the right side sum to: $$2C2^n - \frac{3C}{4}2^n + 2^n = \left(2C - \frac{3C}{4} + 1\right)2^n = \left(\frac{8C - 3C}{4} + 1\right)2^n = \left(\frac{5C}{4} + 1\right)2^n$$ 7. **Step 6: Simplify terms involving $$n$$** On the right side, the $$n$$ terms are: $$4D(n-1) - 3D(n-2) + n = 4Dn - 4D - 3Dn + 6D + n = (4D - 3D)n + (-4D + 6D) + n = Dn + 2D + n$$ 8. **Step 7: Simplify constant terms** On the right side, the constants are: $$4E - 3E + 3 = E + 3$$ 9. **Step 8: Equate coefficients on both sides** Left side: $$C2^n + Dn + E$$ Right side: $$\left(\frac{5C}{4} + 1\right)2^n + (D + 1)n + (2D + E + 3)$$ Equate coefficients: - For $$2^n$$: $$C = \frac{5C}{4} + 1$$ - For $$n$$: $$D = D + 1$$ - For constants: $$E = 2D + E + 3$$ 10. **Step 9: Solve for $$C, D, E$$** From $$n$$ coefficient: $$D = D + 1 \implies 0 = 1$$ which is impossible, so we must modify our guess for the particular solution. Since the right side has a linear term $$n$$, and the homogeneous solution has a constant term, we try a particular solution of the form: $$a_n^p = C2^n + Dn^2 + En + F$$ 11. **Step 10: Substitute new particular solution** Calculate: $$a_n^p = C2^n + Dn^2 + En + F$$ $$a_{n-1}^p = C2^{n-1} + D(n-1)^2 + E(n-1) + F$$ $$a_{n-2}^p = C2^{n-2} + D(n-2)^2 + E(n-2) + F$$ Substitute into recurrence: $$C2^n + Dn^2 + En + F = 4\left(C2^{n-1} + D(n-1)^2 + E(n-1) + F\right) - 3\left(C2^{n-2} + D(n-2)^2 + E(n-2) + F\right) + 2^n + n + 3$$ 12. **Step 11: Simplify $$2^n$$ terms** As before: $$4C2^{n-1} - 3C2^{n-2} + 2^n = \left(\frac{5C}{4} + 1\right)2^n$$ 13. **Step 12: Expand and simplify quadratic terms** $$(n-1)^2 = n^2 - 2n + 1$$ $$(n-2)^2 = n^2 - 4n + 4$$ So: $$4D(n-1)^2 - 3D(n-2)^2 = 4D(n^2 - 2n + 1) - 3D(n^2 - 4n + 4) = 4Dn^2 - 8Dn + 4D - 3Dn^2 + 12Dn - 12D = (4D - 3D)n^2 + (-8D + 12D)n + (4D - 12D) = Dn^2 + 4Dn - 8D$$ 14. **Step 13: Simplify linear terms** $$4E(n-1) - 3E(n-2) = 4En - 4E - 3En + 6E = (4E - 3E)n + (-4E + 6E) = En + 2E$$ 15. **Step 14: Simplify constants** $$4F - 3F = F$$ 16. **Step 15: Combine all right side terms** $$\left(\frac{5C}{4} + 1\right)2^n + Dn^2 + 4Dn - 8D + En + 2E + F + n + 3$$ Group terms: $$2^n: \left(\frac{5C}{4} + 1\right)2^n$$ $$n^2: Dn^2$$ $$n: 4Dn + En + n = (4D + E + 1)n$$ Constants: $$-8D + 2E + F + 3$$ 17. **Step 16: Equate coefficients with left side** Left side: $$C2^n + Dn^2 + En + F$$ Right side: $$\left(\frac{5C}{4} + 1\right)2^n + Dn^2 + (4D + E + 1)n + (-8D + 2E + F + 3)$$ Equate coefficients: - $$2^n: C = \frac{5C}{4} + 1$$ - $$n^2: D = D$$ (always true) - $$n: E = 4D + E + 1 \implies 0 = 4D + 1 \implies D = -\frac{1}{4}$$ - Constants: $$F = -8D + 2E + F + 3 \implies 0 = -8D + 2E + 3$$ 18. **Step 17: Solve for $$C$$** $$C = \frac{5C}{4} + 1 \implies C - \frac{5C}{4} = 1 \implies -\frac{C}{4} = 1 \implies C = -4$$ 19. **Step 18: Solve for $$E$$** From constants equation: $$0 = -8D + 2E + 3$$ Substitute $$D = -\frac{1}{4}$$: $$0 = -8 \cdot \left(-\frac{1}{4}\right) + 2E + 3 = 2 + 2E + 3 = 2E + 5$$ So: $$2E = -5 \implies E = -\frac{5}{2}$$ 20. **Step 19: Particular solution** $$a_n^p = -4 \cdot 2^n - \frac{1}{4} n^2 - \frac{5}{2} n + F$$ 21. **Step 20: Use initial conditions to find $$A, B, F$$** General solution: $$a_n = a_n^h + a_n^p = A3^n + B + a_n^p = A3^n + B - 4 \cdot 2^n - \frac{1}{4} n^2 - \frac{5}{2} n + F$$ Use $$a_0 = 1$$: $$a_0 = A3^0 + B - 4 \cdot 2^0 - \frac{1}{4} 0^2 - \frac{5}{2} 0 + F = A + B - 4 + F = 1$$ Use $$a_1 = 4$$: $$a_1 = A3^1 + B - 4 \cdot 2^1 - \frac{1}{4} 1^2 - \frac{5}{2} 1 + F = 3A + B - 8 - \frac{1}{4} - \frac{5}{2} + F = 4$$ Simplify constants: $$-8 - \frac{1}{4} - \frac{5}{2} = -8 - 0.25 - 2.5 = -10.75$$ So: $$3A + B + F - 10.75 = 4 \implies 3A + B + F = 14.75$$ 22. **Step 21: Solve system for $$A, B, F$$** From $$a_0$$: $$A + B + F = 5$$ From $$a_1$$: $$3A + B + F = 14.75$$ Subtract first from second: $$(3A + B + F) - (A + B + F) = 14.75 - 5 \implies 2A = 9.75 \implies A = 4.875$$ Substitute $$A$$ back: $$4.875 + B + F = 5 \implies B + F = 0.125$$ 23. **Step 22: Determine $$F$$** Recall from step 19 that $$F$$ is part of the particular solution and must satisfy the constants equation: $$0 = -8D + 2E + 3$$ We already used this to find $$E$$, so $$F$$ is free to be absorbed into $$B$$. Thus, set $$F = 0$$ for simplicity, then $$B = 0.125$$. 24. **Final solution:** $$\boxed{a_n = 4.875 \cdot 3^n + 0.125 - 4 \cdot 2^n - \frac{1}{4} n^2 - \frac{5}{2} n}$$ This is the explicit formula for $$a_n$$ satisfying the given recurrence and initial conditions.