I have the sequence $l_{n+1} = 3l_n+1$ for $l_0 = 0$ or $1$ (This just shifts the sequence one index back or forward.) The first terms are $(0),1,4,13,40,121,364,\ldots$
So I am looking for an expression for $S(x) = \sum\limits_{n=0}^\infty l_n x^n$ I tried to standard approach:
$$\begin{align}l_{n+1} &= 3l_n +1 \\ \implies \sum\limits_{n=0}^\infty x^{n+1}l_{n+1} &= \sum\limits_{n=0}^\infty 3l_n x^{n+1}+x^{n+1} \\ \implies S(x)-l_0 &= 3xS(x)+\left(\frac 1 {1-x} -1\right) \\ &= 3xS(x)+\frac{1+x}{1-x}\\ \implies (1-3x)S(x) &= \frac{1+x}{1-x}+l_0 \\ \implies S(x) &= \frac{1+x}{(1-3x)(1-x)}+\frac{l_0}{1-3x} \end{align} $$
But the Taylor series of $S$ for $l_0 = 1$ yields:
$2+8 x+26 x^2+80 x^3+242 x^4+728 x^5+\ldots$ which has a factor $2$ compared to what is desired. (Curiously the same series appears for $l_0 = -1$ , but just a side note.) When we simplify $S(x)$ for $l_0 = 1$ we get $\frac{2}{(1-3x)(1-x)}$ so obviously the right expression for $S$ should be $S(x) = \frac{1}{(1-3x)(1-x)}$
For $l_0 = 0$ we should obviously get the same series multiplied by $x$, but this is not the case, we get:
$1+5 x+17 x^2+53 x^3+161 x^4+485 x^5+\ldots$
This leads me to the conclusion that I made an error when derivin $S$ but I just could not find it. Please help me find the error! Thank you very much in advance!
Your mistake is that $\sum_{n=0}^{\infty} x^{n+1} = \frac{x}{1-x}$, not $\frac{1+x}{1-x}$.
Fixing that, the rest of the steps are:
$$S(x) = \frac{l_0}{1 - 3x} + \frac{x}{(1-x)(1-3x)}$$
With $l_0 = 0$, that's:
$$\begin{split} S(x) &= \frac{-\frac12}{1-x} + \frac{\frac12}{1-3x} \\ &= -\frac12\sum_{n=0}^{\infty}x^n + \frac12\sum_{n=0}^{\infty}(3x)^n \\ &= \sum_{n=0}^{\infty}\frac{3^n-1}2x^n \end{split}$$
So your series is $l_n = \frac{3^n - 1}2$.
If $l_0 = 1$, the coefficient of the $\frac1{1-3x}$ term becomes $\frac32$ , instead of $\frac12$, so we'd end up with $l_n = \frac{3^{n+1} - 1}2$ instead.