# How can I determine the sequence which has this generating function?

In a discrete mathematics past paper, I must find the first eight terms of the sequence whose generating function is $$\frac{x^2}{(1-x)(1-2x)}.$$

I have looked at both of the following posts:

A comment from the first post states that 'To compute the term $a_n$ in the sequence generated by an ordinary generating function, take the $n$-th derivative of the function at $x=0$ and divide by $n!$.'
I haven't tried to use this method in my case, because I would like to see a justification for it, rather than simply memorising and using it.

An answer from the second post refers to updating the affected terms in a simpler generating function; however, I am not sure if that would be useful in my case.

I would appreciate help to understand how to efficiently solve this problem.

• $$\frac{x^2}{(1-x)(1-2x)}=x\cdot\frac1{1-2x}-x\cdot\frac1{1-x}=\ldots$$ – Did May 20 '15 at 18:18
• I must admit this is more elegant than my solution. – Tim Raczkowski May 20 '15 at 18:53

Expanding on Did's comment: \begin{align} \frac{x^2}{(1-2x)(1-x)} &= x \, \frac{1}{1-2x} - x \, \frac{1}{1-x} \\ &= x \sum_{n=0}^{\infty} 2^n x^n - x \sum_{n=0}^{\infty} x^n \\ &= \sum_{k=1}^{\infty} (2^{k-1}-1) x^k \end{align} Thus the first eight terms $a_0,\dotsc,a_7$ of the sequence $(a_k)_{k\geq0}$ are $$0, 0, 1, 3, 7, 15, 31, 63$$

Using the geometric series,

$$\frac1{1-x}=\sum_{n=0}^\infty x^n$$ and $$\frac1{1-2x}=\sum_{n=0}^\infty 2^nx^n.$$

Now, multiply this series and then multiply by $x^2$ and list the first 8 coefficients of the resulting series.

To multiply two power series, $\sum a_nx^n$ and $\sum b_nx^n$.

\begin{align} & (a_0+a_1x+a_2x^2+\ldots)(b_0+b_1x+b_2x^2+\ldots)\\ = & (a_0b_0+a_0b_1x+a_0b_2x^2+\ldots)+(a_1b_0x+a_1b_1x^2+a_1b_2x^3+\ldots)+\ldots\\ + & (a_nb_0x^n+a_0b_1x^{n+1}+a_nb_2x^{n+2}+\ldots)+\ldots \end{align}

Now we need to collect like terms. Notice that the power of $x$ any of the terms is the same as the sum of the indices of $a$ and $b$. In other words, each term has the form $a_jb_kx^{j+k}$. So,

$$a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\ldots....$$

• I had managed to use the geometric series in the way that your answer describes. However, the problem I was having was that I wasn't sure how to multiply the two series. How does one multiply summations, such as the two in your answer? – Caleb Owusu-Yianoma May 20 '15 at 19:34
• @CKKOY Essentially in the same way as one multiplies polynomials. The computation is a bit tedious, though. – A.P. May 20 '15 at 19:38
• @CKKOY A.P. is right, but I'll edit my answer to show you. Also, Did's answer is a bit easier to do, but this sort of multiplication is a tool you should have. – Tim Raczkowski May 20 '15 at 19:41
• @A.P.: You are right! Doing such a multiplication up to the term $x^8$ is a tedious process. – Caleb Owusu-Yianoma May 20 '15 at 19:43