# 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?

• No. The +1 is not part of the quadratic you need to solve to get the general solution. First find a particular solution to eliminate it. – almagest Dec 3 '19 at 9:42
• The characteristic equation of the homogenized equation is $r^3-3r+2=0$. – Christian Blatter Dec 3 '19 at 9:42

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.

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

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

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.