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?

| cite | improve this question | | | | |
$\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.

| cite | improve this answer | | | | |
$\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$.

| cite | improve this answer | | | | |
$\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$$

| cite | improve this answer | | | | |
$\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.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | | | | |
$\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.