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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.