2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – almagest Dec 3 '19 at 9:42
  • 1
    $\begingroup$ The characteristic equation of the homogenized equation is $r^3-3r+2=0$. $\endgroup$ – Christian Blatter Dec 3 '19 at 9:42
3
$\begingroup$

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.

enter image description here

That led me to hypothesize that $a_n=2^{n+1}-n$, which I then easily proved by induction.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.