# Check solution of recurrence relation $a_0 = 3$, $a_1 = 7$, $a_n = 3a_{n-1} - 2a_{n-2}$ for $n \geq 2$

$a_0 = 3, a_1 = 7, a_n = 3a_{n-1} - 2a_{n-2}$ for $n \geq 2$

I know I've got the wrong answer because my outputs don't match. So if someone could show me where I'm going wrong I would be super grateful.

Let $y = \sum\limits_{n = 0}^{\infty} a_nx^n$

multiplying original formula through by $x^n$ I get

$a_nx^n = 3a_{n-1}x^n - 2a_{n-2}x^n$

sum over $n \geq 2$

$\sum\limits_{n \geq 2} a_nx^n = \sum\limits_{n \geq 2} 3a_{n-1}x^n - \sum\limits_{n \geq 2}2a_{n-2}x^n$

The left hand side is equal to $y - a_1 - a_0$

The first part of the right hand side

$\sum\limits_{n \geq 2} 3a_{n-1}x^n = 3x \sum\limits_{n \geq 2} a_{n-1}x^{n-1} = 3x(y-a_0)$

The second part of the right hand side

$\sum\limits_{n \geq 2}2a_{n-2}x^n = 2x^2\sum\limits_{n \geq 2}a_{n-2}x^{n-2} = 2x^2y$

So putting it all together and substituting for $a_0$ and $a_1$

$y - 10 = 3x(y-3) - 2x^2y$

all the $y$'s to one side

$y - 3xy + 2x^2y = -9x + 10 \Rightarrow y = \cfrac{-9x + 10}{(1-2x)(1-x)}$

after fraction decomposition I get

$y = \cfrac{11}{(1-2x)}-\cfrac{1}{(1-x)}$

Which then gives me

$a_n = 11 \cdot 2^n -1$

which is definitely wrong :(

• Your sums are infinite and diverging, and you're equating them. I haven't looked through all your calculations, but that's a red flag. Instead, why not do the standard thing, assume $a_n = r^n$, get a quadratic equation in $r$ and solve that? Commented Oct 18, 2017 at 6:36
• @Arthur It's a homework assignment and so I have to do it this way :( Commented Oct 18, 2017 at 6:38
• Also, I was a bit quick. There is (hopefully) some small $d>0$ such that if $x \in (-d, d)$ then the sums converge. Commented Oct 18, 2017 at 6:39
• Note near the beginning that the left-hand side is $y-a_0-a_1x$ Commented Oct 18, 2017 at 6:42
• @MarkBennet omg, I totally didn't realize I needed to do that, but thinking about it its obviously clear why....thank you so much! Commented Oct 18, 2017 at 6:45

The error in your working comes early on where you compute the left-hand side. You need $y-a_0-a_1x$ rather than $y-a_0-a_1$ and that should fix things.

Alternatively: $$a_n = 3a_{n-1} - 2a_{n-2} \Rightarrow a_n-2a_{n-1}=a_{n-1}-2a_{n-2}.$$ Change: $b_n=a_n-2a_{n-1}, b_0=1$ to get: $$b_n=b_{n-1} \Rightarrow b_n=1.$$ Hence: $$a_n-2a_{n-1}=1, a_0=3 \Rightarrow a_n=2^{n+2}-1.$$

If you are interested in solving only this particular relation, then you can do it with induction.

First, it is not difficult to gues some starting values: $$a_1 = 3 = 2^2-1$$ $$a_2 = 7= 2^3-1$$ $$a_3 = 3\cdot 7-2\cdot 3 = 15 = 2^4-1$$ $$a_4 = 3\cdot 15-2\cdot 7 = 31 = 2^5-1$$

So it is reasonably to believe that $a_n = 2^n-1$ for each $n$.

Do the induction step from $n-1,n\to n+1$:

$$a_{n+1} = 3\cdot (2^n-1)-2\cdot (2^{n-1}-1) = 2^{n+1}-1$$

and we are done.