How do I solve recurrence relation without characteristic equation? Question:

Solve the recurrence relation
$\ a_n = 3a_{n-1} - 2a_{n-2} + 1 $, for all $\ n \ge 2$
$\ a_0 = 2 $
$\ a_1 = 3 $
Write $\ a_n $ in terms of n

I tried to solve this by finding the characteristic equation, $\ r^2 - 3r + 2 - 1 = 0 $ which is $\ r^2 - 3r + 1 $. However, I can't simplify that further because of the "+ 1" unless I use the quadratic general formula... but the roots will be in fractions and they are definitely not correct compared to the answers..
So I tried to find $\ a_2, a_3, a_4 $ and so on... like this:
$\ a_2 = 3a_1 - 2a_0 + 1 = 3(3) - 2(2) + 1 = 6 $
$\ a_3 = 3a_2 - 2a_1 + 1 = 3(6) - 2(3) + 1 = 13 $
$\ a_4 = 3a_3 - 2a_2 + 1 = 3(13) - 2(6) + 1 = 28 $
and so on...
But it leads me to nowhere as I couldn't find any common pattern between $\ a_2, a_3, a_4 $ and so on, to derive $\ a_n $...
How do I solve recurrence relations like this?

A general way to solve this is given by generating functions. Define:
$\begin{equation*}
  A(z)
   = \sum_{n \ge 0} a_n z^n
\end{equation*}$
Take the recursion, shift so there are no subtractions in indices, multiply by $z^n$ and sum over $n \ge 0$. Recognize the resulting sums, use initial values:
$\begin{align*}
  \sum_{n \ge 0} a_{n + 2} z^n
    &= 3 \sum_{n \ge 0} a_{n + 1} z^n
         - 2 \sum_{n \ge 0} a_n z^n
         + \sum_{n \ge 1} z^n \\
  \frac{A(z) - a_0 - a_1 z}{z^2}
    &= 3 \frac{A(z) - a_0}{z} - 2 A(z) + \frac{1}{1 - z} \\
  \frac{A(z) - 2 - 3 z}{z^2}
    &= 3 \frac{A(z) - 2}{z} - 2 A(z) + \frac{1}{1 - z}
\end{align*}$
Now solve for $A(z)$, write as partial fractions:
$\begin{align*}
  A(z)
   &= \frac{2 - 5 z + 4 z^2}{1 -4 z + 5 z^2 - 2 z^3} \\
   &= \frac{2 - 5 z + 4 z^2}{(1 - z^2) (1 - 2 z)} \\
   &= \frac{2}{1 - 2 z} + \frac{1}{1 - z} - \frac{1}{(1 - z)^2} 
\end{align*}$
We want the coefficient of $z^n$ in the above:
$\begin{align*}
  [z^n] A(z)
    &= [z^n] \frac{2}{1 - 2 z}
         + [z^n] \frac{1}{1 - z}
         - [z^n] \frac{1}{(1 - z)^2} \\
    &= 2 \cdot 2^n
         + 1^n
         - (-1)^n \binom{-2}{n} \cdot 1^n \\
    &= 2^{n + 1} + 1
         - \binom{n + 2 - 1}{2 - 1} \\
    &= 2^{n + 1} + 1
         - (n + 1) \\
    &= 2^{n + 1} - n
\end{align*}$
