Solve the inhomogeneous recurrence relation
a_{n}=3a_{n-1}+n^{2}-3 with a_{0}=1
Any help please? I tried a few different cases which got me nowhere.
You may use the process of symbolic differencing to get a homogeneous recurrence. We are given:
(1) $\displaystyle a_{n}=3a_{n-1}+n^2-3$
Now, replace $\displaystyle n$ with $\displaystyle n+1$ to get:
(2) $\displaystyle a_{n+1}=3a_{n}+(n+1)^2-3$
Now, subtract (1) from (2) to get another recurrence. Repeat this process until you have a homogeneous recurrence, from which you may determine the closed form from the characteristic roots, and then determine the parameters from the initial values.
Think of recurrence equations as being like a discrete type of differential equation.
1) Solve the homogeneous case: $\displaystyle \tilde{a}_n = 3\tilde{a}_{n-1}$ to get $\displaystyle \tilde{a}_n = c3^n.$
2) Now use variation of parameters. Try: $\displaystyle a_n = 3^nb_n \ (\text{with }1 = a_0 = 3^0b_0 = b_0).$
$\displaystyle a_n = 3a_{n-1} + n^2-3 \text{ becomes } 3^nb_n = 3(3^{n-1}b_{n-1}) +n^2-3 = 3^nb_{n-1}+ n^2-3,$
$\displaystyle \text{giving } b_n = b_{n-1}+ \frac{n^2-3}{3^n}, \text{ with }b_0 = 1.$
$\displaystyle \text{That's solveable as a sum: } b_n = b_0 + \sum_{k=1}^n \frac{k^2-3}{3^k} \text{ for } n \ge 1.$
You can further simply that.