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

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