Given the ordinary generating function $G(x) = \frac{1}{(1-x)(1-3x)}$ for some sequence $(a_{k})$, find $a_{k}$.

Question

Textbook answer: $a_{k}=-\frac{1}{2} + \frac{3}{2}3^{k}$

Here is what I did so far:

$G(x) = \frac{1}{(1-x)(1-3x)} = \left ( \sum_{k=0}^{\infty}x^{k} \right )\left ( \sum_{k=0}^{\infty}(3x)^{k} \right )$

$= 3^{k}\left ( \sum_{k=0}^{\infty}x^{k} \right )\left ( \sum_{k=0}^{\infty}x^{k} \right )=3^{k}\left ( \sum_{k=0}^{\infty}x^{k} \right )^{2}$

$= 3^{k}(1+x^{2}+x^{3}+\cdots)$

$= 3^{k}(1+x+x^{2}+x^{3}+\cdots)-x$ $= 3^{k}\frac{1}{1-x}-x$

But how did they get the $x=-\frac{1}{2}$ and $\frac{1}{1-x}=\frac{3}{2}$?

Answer 1

Many of the steps above are careless errors and irrecoverably wrong. Here is how to do it:

You have: $$ G(x)= \left(\sum x^k\right)\left(\sum 3^k x^k\right) $$

So you realise this is a convolution and work out the coefficient of $x^k$:

$$ G(x) = \sum_{k=0} \left(\sum_{\ell=0}^k x^{k-\ell}3^\ell x^\ell\right) $$

$$ G(x) = \sum_{k=0} x^k \left(\sum_{\ell=0}^k 3^\ell \right) $$

Now we can simplify the inner sum as we know $\sum_{\ell=0}^k 3^\ell = \frac{3^{k+1}}{2}-\frac 12$ and the result follows

Answer 2

They most likely just wrote it as a partial fractions, such as: $$ \frac{1}{(1-x)(1-3x)} =-\frac{1}{2} \frac{1}{1-x}+\frac{3}{2}\frac{1}{1-3x} $$ from which it is clear that $$ G(x)=-\frac{1}{2}\sum_{k\geq 0}{x^k}+\frac{3}{2}\sum_{k\geq 0}{(3x)^k} = \sum_{k\geq 0}\left(-\frac{1}{2}+\frac{3}{2}3^k\right)x^k. $$