2
$\begingroup$

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:

  1. How can I determine the sequence generated by a generating function?
  2. how to determine the sequence generated by these generating functions?

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.

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

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 $$

$\endgroup$
2
$\begingroup$

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....$$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Caleb Owusu-Yianoma May 20 '15 at 19:34
  • 1
    $\begingroup$ @CKKOY Essentially in the same way as one multiplies polynomials. The computation is a bit tedious, though. $\endgroup$ – A.P. May 20 '15 at 19:38
  • 1
    $\begingroup$ @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. $\endgroup$ – Tim Raczkowski May 20 '15 at 19:41
  • $\begingroup$ @A.P.: You are right! Doing such a multiplication up to the term $x^8$ is a tedious process. $\endgroup$ – Caleb Owusu-Yianoma May 20 '15 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.