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?