Combinatorics generating functions of a series

Question

Hi I found that the generating function of a series $a_n$ is:

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

I need to find a formula for $a_n$.

I tried some things and found that the generating function is equal to:

$$\frac{1}{3}\cdot (1+2x)\cdot( \frac{2}{1+3x} + \frac{1}{1-3x})$$

but I cant get any further than that.

Answer 1

Hint: use partial fractions to rewrite as $$\frac{2}{9}+\frac{2/9}{1-(-3x)}+\frac{5/9}{1-3x}.$$

Answer 2

We start from the generating function: $$f(x)=\frac{(1-x)(1+2x)}{(1+3x)(1-3x)} = (1-x)\frac{(1+2x)}{(1+3x)(1-3x)} $$ The denominator of the fraction has the zeroes $1/3,-1/3$. Their reciprocals are therefore $3,-3$.

Therefore the explicit formula for $\frac{(1+2x)}{(1+3x)(1-3x)} $ has the form $$ a_n = \alpha\cdot (3)^n + \beta \cdot(-3)^n $$

We have $$ a_0 = \frac{(1+2x)}{(1+3x)(1-3x)} \bigg|_{x=0} =1\\ a_1 = \frac d {dx}\frac{(1+2x)}{(1+3x)(1-3x)} \bigg|_{x=0} = 2$$

And therefore obtain the linear equation system $$ 1 = \alpha + \beta \\ 2 = \alpha\cdot (3) + \beta \cdot(-3) $$

And with it the explicit formula $$\frac{(1+2x)}{(1+3x)(1-3x)} = \sum_{n\ge 0} 5/6·3^n + 1/6·(-3)^n x^n $$

Therefore, we have: $$ f(x) = (1-x)\frac{(1+2x)}{(1+3x)(1-3x)} = (1-x) \sum_{n\ge 0} 5/6·3^n + 1/6·(-3)^n x^n \\ = (\sum_{n\ge 0} 5/6·3^n + 1/6·(-3)^n x^n) - (\sum_{n\ge 0} 5/6·3^n + 1/6·(-3)^n x^{n+1}) \\ =1+\sum_{n\ge 1} (5/6·3^n + 1/6·(-3)^n - (5/6·3^{n - 1} + 1/6·(-3)^{n - 1})) x^n $$

Answer 3

Your approach is fine. We see or obtain with polynomial division \begin{align*} 1+2x=\frac{2}{3}(1+3x)+\frac{1}{3}\quad&\Longrightarrow\quad\frac{1+2x}{1+3x}=\frac{2}{3}+\frac{1}{3(1+3x)}\\ 1+2x=-\frac{2}{3}(1-3x)+\frac{5}{3}\quad&\Longrightarrow\quad\frac{1+2x}{1-3x}=-\frac{2}{3}+\frac{5}{3(1-3x)}\tag{1} \end{align*}

We start with OPs expression and obtain with (1) and the geometric series expansion \begin{align*} \color{blue}{\frac{1}{3}}&\color{blue}{(1+2x)\left( \frac{2}{1+3x} + \frac{1}{1-3x}\right)}\\ &=\frac{2}{3}\cdot\frac{1+2x}{1+3x}+\frac{1}{3}\cdot\frac{1+2x}{1-3x}\\ &=\frac{2}{3}\left(\frac{2}{3}+\frac{1}{3(1+3x)}\right)+\frac{1}{3}\left(-\frac{2}{3}+\frac{5}{3(1-3x)}\right)\\ &=\frac{2}{9}+\frac{2}{9}\sum_{n=0}^\infty(-3)^nx^n+\frac{5}{9}\sum_{n=0}^\infty 3^nx^n\\ &\,\color{blue}{=\frac{2}{9}+\sum_{n=0}^\infty\frac{1}{9}\left(2(-1)^n+5\right)3^nx^n} \end{align*}