1

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!

flawr
  • 16,533
  • 5
  • 41
  • 66

1 Answers1

1

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.

Barry
  • 2,268
  • Thanks a lot! As I said, I just do not know how I missed such a simple mistake=) And thanks for finishing the calculation, this is saving me some work! =) – flawr Jun 04 '15 at 18:25