How to solve this recurrence relation $f_n = 13{f_{n-2}} + 12{f_{n - 3}} + 2n + 1$?

Question

$f_n = 13f_{n-2} + 12f_{n - 3} + 2n + 1$

Ok so first I was to find the solution for the $13f_{n-2} + 12f_{n - 3}$ portion. There are 3 roots, however, so I am not sure which ones to use in my general solution. Also, I'm stuck trying to find the particular solution for the $ 2n + 1$ portion. If anyone could guide me in solving this recurrence, I would very grateful! Thanks!

Answer 1

I rewrite the relation (for personal preference) as: $$f_{n+3} - 13{f_{n+1}} - 12{f_{n}} = 2(n+3) + 1=2n+7,$$ which is valid for $n\ge0$. Then the characteristic polynomial is $r^3 - 13r-12=0$ whose roots are $r=-3,-1,4$. We use all of the roots since the relation is of order $3$. So the complementary solution to the corresponding homogenous recurrence relation is $$f^c_n = a_1(-3)^n +a_2 (-1)^n+ a_34^n.$$

Now assume the particular solution is of the form $f_n = sn+t$. Then $f_{n+1} = sn+s+t$, and $f_{n+3} = sn + 3s+t$. We can substitute these back into the original relation, match coefficients with respective powers of $n$, and solve for both $s$ and $t$: $$sn+3s+t-13(sn+s+t) -12(sn+t) = 2n+7.$$ We find that $s=-\frac{1}{12}$ and $t=-\frac{37}{144}$.

Now adding the particular and complementary solutions is the general solution to our original recurrence relation.

Answer 2

If you try a linear expression, $f_n=a+bn$, $$a+bn=13(a+b(n-2))+12(a+b(n-3))+2n+1=25a-62b+1+(25b+2)n.$$ By identification, $$a=25a-62b+1,\\b=25b+2.$$