Where is my error in using generating functions to solve this recurrence relation?

Question

Let $T(n)=2T(n-1)+n$, $T(1)=1$. It is known that $T(n) = 2^{n+1}-(n+2)$. However, my attempt yields something different: let $f(z)=\sum_{n=0}^\infty T(n)z^n$ and sum both sides of the recurrence over $n\geqslant1$: $$ \sum_{n=1}^\infty T(n)z^n = 2\sum_{n=1}^\infty T(n-1)z^n + \sum_{n=1}^\infty nz^n $$ or $$ f(z) - T(1) = 2zf(z) +\frac z{(1-z)^2}, $$ hence $$f(z) = \frac1{1-2z} + \frac z{(1-2z)(1-z)^2}. $$ Partial fraction decomposition yields \begin{align} f(z) &= \frac1{1-2z} + \frac2{1-2z}-\frac1{1-z}-\frac1{(1-z)^2}\\ &= \frac3{1-2z}-\frac1{1-z}-\frac1{(1-z)^2}\\ &= 3\sum_{n=0}^\infty 2^nz^n - \sum_{n=0}^\infty z^n -\sum_{n=0}^\infty (n+1)z^n\\ &= \sum_{n=0}^\infty (3\cdot 2^n - (n+2))z^n. \end{align} Somehow I have a factor of $3$ that is not in the correct expression. Where is my error?

Answer 1

The left-hand side of your second displayed equation should be $f(z)-T(0)$, not $f(z)-T(1)$. If you correct that error through to the end you will indeed end up with $2^{n+1}-(n+2)$.