2
$\begingroup$

I am currently working my way through An Introduction to Analysis of Algorithms to stay sharp with recurrences as well as learn generating function techniques. However my analyses and the books analyses for the first few sample problems on ordinary generating functions differ. I've checked and rechecked [my work as well as errata on the webpage], but cannot see how the authors made certain leaps. For example:

Given the recurrence $a_{n} = a_{n-1} + 1$ for $n \geq 1$ with $a_0 = 0$ and letting $A(z) = \sum_{n \geq 0} a_n z^n$ I have the following steps: $$ \begin{align*} \sum_{n \geq 1} a_n z^n &= \sum_{n \geq 1} a_{n-1} z^n + \sum_{n \geq 1} z^n \\ A(z) - a_0&= zA(z) + \frac{z}{1-z} \\ A(z)(1 - z) &= \frac{z}{1-z} + a_0\\ A(z) &=\frac{z}{(1-z)^2} + \frac{a_0}{1-z} \end{align*}$$

Since $a_0 = 0$ we just end up with $$A(z) = \frac{z}{(1-z)^2} \\ a_n = n$$.

However, the authors' derivation is the following: $$ \begin{align*} \sum_{n \geq 1} a_n z^n &= \sum_{n \geq 1} a_{n-1} z^n + \frac{1}{1-z} \\ A(z) - 1 &= zA(z) + \frac{1}{1-z} \\ A(z) &= \frac{z}{(1-z)^2} \\ a_n &= n\\ \end{align*}$$ Am I crazy, how did they get $A(z) - 1$ in the 2nd step? They do the exact same thing in the next example for $a_n = 2a_{n-1} + 1$. Is this just a typo? I would expect them to subtract $a_0z^0 = a_0$. Where did that $-1$ come from?

$\endgroup$
  • 2
    $\begingroup$ You're right, they had a typo. Your derivation is correct. $\endgroup$ – Yuval Filmus Aug 28 '12 at 22:31
3
$\begingroup$

This answer is just so that the question is not left unanswered.

The OP is correct: the book got it wrong.

$\endgroup$

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.