Finding a closed form for a recursive sequence using generating functions - where is my mistake?

Question

I have solved dozens of those problems before which makes it even more confusing.

The recursive sequence is defined as follows: $a_0=0$

$a_n=3a_{n-1}+1$

If I define $F(x)=$$\sum_{n=0}^{\infty} a_nx^n$, I get:

$F(x)=3xF(x)+\frac{1}{1-x}$

$F(x)=\frac{1}{(1-x)(1-3x)}=\frac{3}{2(1-3x)}-\frac{1}{2(1-x)}$

And now:

$F(x)=\frac{3}{2}\sum_{n=0}^{\infty} 3^nx^n-\frac{1}{2}\sum_{n=0}^{\infty} x^n$

$F(x)=\sum_{n=0}^{\infty} \frac{3^{n+1}-1}{2}x^n$

Which gives $a_n=\frac{3^{n+1}-1}{2}$.

The corrent answer is $a_n=\frac{3^{n}-1}{2}$, which means something went wrong along the way, where is my error?

Answer 1

You have to be careful with the first term of the series. I think $F(x)=3xF(x)+\frac x {1-x}$.

Answer 2

Your mistake is already pointed out in a previous comment. I leave another suggestion: Why not solving it instead as a linear difference equation with constant coefficients? The solution is written as the sum of the general solution of the homogeneous equation ($y_n$) with a particular solution of the original equation ($p_n$) (the same process as in linear differential equations)... $$ a_n =y_n+p_n = c 3^n -\frac 12 $$

where $c$ can be computed from the initial condition $a_0=0 \Leftrightarrow c= \frac 12$, which leads to $a_n = \frac 12 (3^n - 1)$.