0
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2015 at 18:56

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks! That was very clear. $\endgroup$
    – Kamil
    Jan 27, 2015 at 19:01
  • $\begingroup$ @Kamil: You’re welcome! $\endgroup$ Jan 27, 2015 at 19:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .