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.
 A: Well you've made a mistake,I'm not sure where is your mistake anyway here's is a different solution
$$a_n=3a_{n-1}+n^2-3\\a_{n-1}=3a_{n-2}+n^2-2n-2\\a_n-a_{n-1}=3a_{n-1}+n^2-3-3a_{n-2}-n^2+2n+2\\a_n=4a_{n-1}-3a_{n-2}+2n-1\\a_{n-1}=4a_{n-2}-3a_{n-3}+2n-3\\a_n-a_{n-1}=4a_{n-1}-3a_{n-2}+2n-1-4a_{n-2}+3a_{n-3}-2n+3\\a_n=5a_{n-1}-7a_{n-2}+3a_{n-3}+2\\a_n=5a_{n-1}-7a_{n-2}+3a_{n-3}+2\\a_{n-1}=5a_{n-2}-7a_{n-3}+3a_{n-4}+2\\a_n-a_{n-1}=5a_{n-1}-7a_{n-2}+3a_{n-3}+2-5a_{n-2}+7a_{n-3}-3a_{n-4}-2\\a_n=6a_{n-1}-12a_{n-2}+10a_{n-3}-3a_{n-4}\\t^4-6t+12t-10t+3=0\\t_{1,2,3}=1\\t_4=3\\a_n=C_1+nC_2+n^2C_3+C_43^n\\1=C_1+C_4\\a_1=1,a_2=4,a_3=18\\a_1=C_1+C_2+C_3+3C_4\\a_2=C_1+2C_2+4C_3+9C_4\\a_3=C_1+3C_2+9C_3+27C_4\\C_1=0,C_2=-\frac{3}{2},C_3=-\frac{1}{2},C_4=1\\a_n=-\frac{3}{2}n-\frac{1}{2}n^2+3^n$$
A: Given the homogenous solution: $a_n^{(h)} = c_03^n$ and the particular solution: $a_n^{(p)} = c_1n^2+c_2n+c_3$, and we have: $a_n = a_n^{(h)}+a_n^{(p)}$. First we find the coefficients to the particular solution:
$$
\begin{align}
&a_n^{(p)} \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:- 3a_{n-1}^{(p)} &&= n^2+0n-3\\
\iff &c_1n^2+c_2n+c_3 -3\left(c_1(n-1)^2+c_2(n-1)+c_3\right) &&= n^2+0n-3\\
\iff &c_1n^2+c_2n+c_3 -3(c_1n^2-2c_1n+c_1+c_2n-c_2+c_3) &&= n^2+0n-3\\
\iff &\color{red}{c_1}n^2\color{green}{+c_2}n\color{blue}{+c_3}\color{red}{-3c_1}n^2\color{green}{+6c_1}n\color{blue}{-3c_1}\color{green}{-3c_2}n\color{blue}{+3c_2}\color{blue}{-3c_3} &&= n^2+0n-3\\
\iff &\color{red}{(-2c_1)}n^2+\color{green}{(6c_1-2c_2)}n+\color{blue}{(3c_1-3c_2+4c_3)} &&= \color{red}{1}n^2\color{green}{+0}n\color{blue}{-3}\\
\end{align}
$$
This gives three equations:
$$
\begin{matrix}
\color{red}{-2c_1}&&&= \color{red}{1}\\ \color{green}{6c_1}&\color{green}{-2c_2}&&= \color{green}{0}\\ \color{blue}{3c_1}&\color{blue}{-3c_2}&\color{blue}{+4c_3}&= \color{blue}{3}
\end{matrix}
$$
Solving this system yields:
$$
\begin{matrix}
c_1&&&=-\frac{1}{2}\\ &c_2&&= -\frac{3}{2}\\ &&c_3&= 0
\end{matrix}
$$
So we have $a_n^{(p)} = - \frac{1}{2}n^2-\frac{3}{2}n+0$
This means a solution is given by $a_n = c_03^n - \frac{1}{2}n^2-\frac{3}{2}n$, and given the initial condition $a_0 = 1$, we can solve this for $c_0$:
$a_0 = 1 = c_03^0 - \frac{1}{2}0^2 - \frac{3}{2}0 \iff c_0 = 1$
This means $a_n = 3^n - \frac{1}{2}n^2-\frac{3}{2}n$
A: $$ a_n = 3a_{n-1} + n^2 - 3 = 3^ka_{n-k} + n^2 + 3(n - 1)^2 + \ldots + 3^{k - 1}(n - k + 1)^2 - (3 + \ldots + 3^k)   $$
$$ a_n = 3^ka_{n - k} + \sum_{m=0}^{k-1}3^m(n - m)^2 - \sum_{m = 0}^{k-1}3^{m+1}$$
Setting $k = n$, we have
$$a_n = 3^n + \sum_{m=0}^{n-1}3^m(n - m)^2 - \sum_{m = 0}^{n-1}3^{m+1} = \frac{1}{2}(-n^2 - 3n + 3^{n+1} - 3) - \frac{3}{2}(3^n - 1) + 3^n.$$ 
The last was calculated using numerical software. Simplifying we have,
$$\frac{1}{2}(-n^2 - 3n + 3^{n+1} - 3) - \frac{3}{2}(3^n - 1) + 3^n = 3^n - \frac{1}{2}n^2 - \frac{3}{2}n.$$
A: 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.
