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?
