Solving $a_n=3a_{n-1}-2a_{n-2}+3$ for $a_0=a_1=1$

Question

I'm trying to solve the recurrence $a_n=3a_{n-1}-2a_{n-2}+3$ for $a_0=a_1=1$. First I solved for the homogeneous equation $a_n=3a_{n-1}-2a_{n-2}$ and got $\alpha 1^n+\beta 2^n=a_n^h$. Solving this gives $a_n^h =1$. The particular solution, as I understand, will be $a_n^*=B$ since $f(n)=3\times 1^n$. But then I get $B=a^*=3a^*_{n-1}-2a^*_{n-2}+3=B+3$. This has to be a mistake, but I don't see what I did wrong.

Answer 1

Hint: Look for a particular solution of the shape $a_n^\ast=Bn$. You should get $B=-3$.

Answer 2

$$a_n - a_{n-1}+3=2(a_{n-1}-a_{n-2}+3)$$ $$a_n - a_{n-1}+3=2^{n-1}(a_1-a_0+3)=3\cdot 2^{n-1}$$ $$\\$$ $$a_n = a_{n-1} + 3\cdot (2^{n-1}-1)$$ $$a_{n-1} = a_{n-2} + 3\cdot (2^{n-2}-1)$$ $$...$$ $$a_1 = a_0 + 3\cdot (2^0-1)$$ Adding side by side, $$a_n=a_0+3\cdot (2^0+2^1+...+2^{n-1}-n)$$ $$=1+3\cdot (2^n-1-n)=3\cdot2^n-3n-2$$

Answer 3

Let $f(x) = \sum_{n=0}^\infty a_nx^n$. Multiplying the recurrence by $x^n$ and summing over $n\geqslant 2$ we find that the LHS is $$\sum_{n=2}^\infty a_nx^n = f(x)-1-x $$ and the RHS is $$3\sum_{n=2}^\infty a_{n-1}x^n - 2\sum_{n=2}^\infty a_{n-2}x^n + 3\sum_{n=2}^\infty x^n = 3x(f(x)-1) - 2x^2f(x)+\frac{3x^2}{1-x}. $$ Equating the above and $f(x)$ we find that $$f(x) = \frac{1-2x}{1-3x+2x^2} + \frac{3x^2}{(1-x)(1-3x+2x^2)}. $$ Partial fraction decomposition yields $$f(x) = \frac1{1-x} + \frac3{1-2x} - \frac3{(1-x)^2}, $$ which has series representation $$f(x) = \sum_{n=0}^\infty(1+3\cdot(2^n) - 3(n+1))x^n. $$ It follows that $$a_n = 1+3\cdot(2^n) - 3(n+1),\ n\geqslant0. $$

Answer 4

Because of the constant term, define $$b_n=a_n+c n +d$$ Replacing in $$a_n=3a_{n-1}-2a_{n-2}+3$$ leads to $$b_n=3 b_{n-1}-2 b_{n-2}+c+3$$ So, choose $c=-3$ and the recurrence becomes $$b_n=3 b_{n-1}-2 b_{n-2}$$ Then, as usual, the characteristic equation $r^2-3r+2=0$ which has roots $r_1=1$, $r_2=2$. So $$b_n=C_1 \,1^n+C_2 \,2^n=C_1+C_2 \,2^n$$ $$a_n=C_1+C_2 \,2^n-3n$$ Apply the initial conditions $$a_0=C_1+C_2=1\quad \quad \quad a_1=C_1+2C_2-3=1$$ which give $C_1=-2$ and $C_2=3$ which finally give $$a_n=-2+3 \times 2^n-3n$$