<s>[INST] Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$. Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$.
My solutions: the homogeneous portion is $a_n=c3^n$, and the inhomogeneous portion is $a^*_n=-1/2n^2-3/4n+9/8$.
This results in a final recurrence relation of 
$$a_n=-\frac{1}{8}3^n-\frac{1}{2}n^2-\frac{3}{4}n+\frac{9}{8}.$$
I am just wondering if someone could check my work to make sure I have the procedure correct.
 [/INST] Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the shifted recurrence by $ẓ^n$ and sum over $n \ge 0$, recognize some sums:
$\begin{align*}
\sum_{n \ge 0} a_{n + 1} z^n
  &= 3 \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} (n + 1)^2 - 3 \sum_{n \ge 0} z^n \\
\frac{A(z) -a_0}{z}
  &= 3 A(z) + \sum_{n \ge 0} n^2 z^n + 2 \sum_ {n \ge 0} n z^n - 2 \sum_{n \ge 0} z^n
\end{align*}$
You know the geometric sum:
$\begin{align*}
\sum_{n \ge 0} z^n
  &= \frac{1}{1 - z}
\frac{d}{d z} \sum_{n \ge 0} z^n
  &= \sum_{n \ge 0} n z^{n - 1} \\
z \frac{d}{d z} \sum_{n \ge 0} z^n
  &= \sum_{n \ge 0} n z^n \\
  &= \frac{z}{(1 - z)^2}
\sum_{n \ge 0} n^2 z^n
  &= \frac{z + z^2}{(1 - z)^3}
\end{align*}$
Plug this in above, solve for $A(z)$, and write as partial fractions:
$\begin{align*}
A(z)
  &= \frac{1 - z - z^2 - z^3}{(1 - z) (1 + z) (1 - 3 z) (1 + z + z^2)} \\
  &= \frac{7 + 2 z}{39 (1 + z + z^2)}
       + \frac{21}{52 (1 - 3 z)}
       + \frac{1}{4 (1 + z)}
       + \frac{1}{6 (1 - z)} \\
&= \frac{(7 + 2 z) (1 - z)}{39 (1 - z^3)}
       + \frac{21}{52 (1 - 3 z)}
       + \frac{1}{4 (1 + z)}
       + \frac{1}{6 (1 - z)} \\
&= \frac{7 - 5 z - 2 z^2}{39 (1 - z^3)}
       + \frac{21}{52 (1 - 3 z)}
       + \frac{1}{4 (1 + z)}
       + \frac{1}{6 (1 - z)}
\end{align*}$
You want the coefficient of $z^n$ from this. Everything in sight is just a geometric series:
$\begin{align*}
[z^n] \left(
         \frac{7 - 5 z - 2 z^2}{39 (1 - z^3)}
           + \frac{21}{52 (1 - 3 z)}
           + \frac{1}{4 (1 + z)}
           + \frac{1}{6 (1 - z)}
      \right)
  &= (7 [z^n] - 5 [z^{n - 1}] - 2 [z^{n - 2}]) \frac{1}{1 - z^3)}
      + \frac{21}{52} \cdot 3^n
      + \frac{1}{4} \cdot (-1)^n
      + \frac{1}{6} \\
  &= [n = 0] \cdot 7 
      + \frac{21}{52} \cdot 3^n
      + \frac{1}{4} \cdot (-1)^n
      + \frac{1}{6}
\end{align*}$
Here $[n = 0]$ uses Iverson's convention: $1$ if the condition is true, $0$ if false. If $n = 0$, the only relevant term is the first one, if $n > 0$ the other two terms cancel with it.
</s>