Hi, how to solve the following non-homogenous recurrence relation?

Question

f(0) = 5
f(1) = 13
f(n) = 4f(n-1)-3f(n-2)-4n-2 for n≥2

Thanks

Answer 1

f(n) - 4f(n-1) + 3f(n-2) = 4n + 2

First solve the corresponding homogenous system:
f(n) - 4f(n-1) + 3f(n-2) = 0
The auxiliary equation is r^2 - 4r + 3 = 0 <=> (r-3)(r-1) = 0 <=> r = 1 or 3. So the general solution is
f(n) = A.3^n + B.1^n = A.3^n + B.

Now we look for a particular solution. Since the non-homogenous part is 4n + 2, we would try a particular solution of form Cn + D. But the constant term in this is already part of the general solution, so we try instead a particular solution of form Cn^2 + Dn.
If we let f(n) = Cn^2 + Dn, we get
Cn^2 + Dn - 4C(n-1)^2 - 4D(n-1) + 3C(n-2)^2 + 3D(n-2) = 4n + 2
<=> Cn^2 + Dn - 4Cn^2 + 8Cn - 4C - 4Dn + 4D + 3Cn^2 - 12Cn + 12C + 3Dn - 6D = 4n + 2
<=> n^2 (C - 4C + 3C) + n (D + 8C - 4D - 12C + 3D) + (-4C + 4D + 12C - 6D) = 4n + 2
<=> -4C = 4 and 8C - 2D = 2
<=> C = -1 and D = -5
So the general solution is
f(n) = A.3^n + B - n^2 - 5n
Now f(0) = A + B = 5
f(1) = 3A + B - 6 = 13
Solving these gives A = 7, B = -2. So the final solution is
f(n) = 7.3^n - n^2 - 5n - 2.