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: I made a spreadsheet, calculating $a_n$ further than you did, and saw a pattern, 
where $a_n$ became close to powers of $2$.  
I then made an additional column with the difference between $a_n$ and $2^{n+1}$
and saw a further obvious pattern there.  

That led me to hypothesize that $a_n=2^{n+1}-n$, which I then easily proved by induction.
A: This is an inhomogeneous linear recurrence relation. You can solve it by first solving the corresponding homogeneous linear recurrence relation, $a_n=3a_{n-1}-2a_{n-2}$, and adding to its general solution any particular solution of the inhomogeneous relation. In the present case, a particular solution of the inhomogeneous relation can be found using the ansatz $a_k=ck$ and solving for $c$.
A: The relation can be written as
$$(a_n-a_{n-1})-2(a_{n-1}-a_{n-2})=1$$
$$let\,\,a_n-a_{n-1}=2^n.t_n$$
$$t_n-t_{n-1}=\frac{1}{2^n}$$
putting different values of n we get
$$t_n-t_1=\frac{1}{2}(1-\frac{1}{2^{n-1}})$$
Where $t_1=1/2$
$$ Hence\,\,t_n=1-\frac{1}{2^n}$$
$$Hence \,\,a_n-a_{n-1}=2^n-1$$
For different n put in above relation we get
$$a_n=2^{n+1}-n$$
A: Since you tried with pattern-detecting I think it is often better to do the first couple of consecutive iterations with formal variables/indeterminates for the initializations.  I got with this
     a_n           |        b_n            n
 ------------------|--------------------------
     a             |            b          0
           b       | -  2*a+  3*b+  1      1
-  2*a+  3*b+  1   | -  6*a+  7*b+  4      2
-  6*a+  7*b+  4   | - 14*a+ 15*b+ 11      3
- 14*a+ 15*b+ 11   | - 30*a+ 31*b+ 26      4
- 30*a+ 31*b+ 26   | - 62*a+ 63*b+ 57      5
- 62*a+ 63*b+ 57   | -126*a+127*b+120      6
-126*a+127*b+120   | -254*a+255*b+247      7

where I think one can detect the pattern immediately.
A: 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*}$
