Problem: Determine the generating function for the sequence $(a_k)$ given by $a_0 = 2$ and $a_k = 3a_{k-1} - 4$ for $k \geq 1$.

Solution: We define $f(x) = \sum_{k=0}^{\infty} a_k x^k$ for the generating function of the sequence $(a_k)$. Because $a_0 = 2$, we have \begin{align*} f(x) = 2 + \sum_{k=1}^{\infty} a_k x^k. \end{align*} Applying the recurrence relation gives us also \begin{align*} f(x) = 2 + \sum_{k=1}^{\infty} (3a_{k-1} - 4)x^k = 2 + 3 \sum_{k=1}^{\infty} a_{k-1} x^k - 4 \sum_{k=1}^{\infty} x^k. \end{align*} The first series we can rewrite als follows: \begin{align*} \sum_{k=1}^{\infty} a_{k-1} x^k = \sum_{k=0}^{\infty} a_k x^{k+1} = x \sum_{k=0}^{\infty} a_k x^k = x f(x). \end{align*} The second series is \begin{align*} \sum_{k=1}^{\infty} x^k = \frac{x}{1-x}. \end{align*}

This is what I don't understand. I thought we could write the second series as $\frac{x}{1-x}$ only when the index starts running from $o$, i.e. when $k = 0$? What happened with the constant term $1$ in this case?

I'm confused here, so some clarification would be helpful.

  • $\begingroup$ When the indexing starts from zero, that sum is $\dfrac1{1-x}$. In this case, everything gets multiplied by $x$, or use the GP formula. $\endgroup$ – Macavity Jan 27 '15 at 18:56

You can see it in either of two ways.

  • $\displaystyle\sum_{k=1}^\infty x^k$ is a geometric series with first term $x$ and ratio $x$, so its sum is $\frac{x}{1-x}$.

  • $\displaystyle\sum_{k=0}^\infty x^k=\frac1{1-x}$; now multiply both sides by $x$ to get $$\frac{x}{1-x}=\sum_{k=0}^\infty x^{k+1}=\sum_{k=1}^\infty x^k\;.$$

Note that contrary to your assertion, $\displaystyle\sum_{k=0}^\infty x^k$ is not $\dfrac{x}{1-x}$.

  • $\begingroup$ Thanks! That was very clear. $\endgroup$ – Kamil Jan 27 '15 at 19:01
  • $\begingroup$ @Kamil: You’re welcome! $\endgroup$ – Brian M. Scott Jan 27 '15 at 19:03

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.