How do I solve recurrence relation without characteristic equation?

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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$$

Answer 4

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.

Answer 5

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*}$