Need refresher on z-transforms and difference equations I recently tried showing someone else how to solve a difference equation using z-transforms, but it's been a long time and what I was getting didn't look right.  I was trying to solve the recurrence we all know and love
$$x[n]=x[n-1]+x[n-2],x[0]=0,x[1]=1$$
using the one-sided z-transform
$$X(z)=\sum\limits_{n=0}^\infty x[n]z^{-n}$$
So, taking the z-transform of both sides, I got
$$X(z)=\sum\limits_{n=0}^\infty x[n-1]z^{-n}+\sum\limits_{n=0}^\infty x[n-2]z^{-n}=$$
$$z^{-1}\sum_{n=0}^\infty x[n-1]z^{-n+1}+z^{-2}\sum\limits_{n=0}^\infty x[n-2]z^{-n+2}$$
I substitute $i=n+1$ in the first sum, $i=n+2$ in the second
$$X(z)=z^{-1}\sum\limits_{i=1}^\infty x[i]z^{-i}+z^{-2}\sum\limits_{i=2}^\infty x[i]z^{-i}=$$
$$z^{-1}(X(z)-x[0]z^0)+z^{-2}(X(z)-x[0]z^0-x[1]z^{-1})=$$
$$z^{-1}X(z)+z^{-2}X(z)-z^{-3}$$
$$X(z)(1-z^{-1}-z^{-2})=-z^{-3}$$
$$X(z)=-\frac{z^{-3}}{1-z^{-1}-z^{-2}}$$
Did I go wrong somewhere?  If not, how do I proceed from here?
Update:  All right, now that the mistake has been pointed out, let's see if I can correct it and continue.  So the last correct step was
$$X(z)=z^{-1}\sum\limits_{n=0}^\infty x[n-1]z^{-n+1}+z^{-2}\sum\limits_{n=0}^\infty x[n-2]z^{-n+2}$$
Now the substitution here should be $i=n-1$ for the first sum and $i=n-2$ for the second yielding
$$X(z)=z^{-1}\sum\limits_{i=-1}^\infty x[i]z^{-i}+z^{-2}\sum\limits_{i=-2}^\infty x[i]z^{-i}=$$
$$z^{-1}(x[-1]z+X(z))+z^{-2}(x[-2]z^2+x[-1]z+X(z))$$
So if I were to continue like this, I'd have to calculate $x[-2]$ and $x[-1]$.  I'm guessing this is why it was suggested to rewrite it as $x[n+2]=x[n+1]+x[n]$.  In any case, I'm satisfied I can handle it.
 A: (I’ll write $x_n$ instead of $x[n]$.) 
Your mistake was in rewriting $$z^{-1}\sum_{n=0}^\infty x_{n-1}z^{-n+1}\quad\text{ and }\quad z^{-2}\sum\limits_{n=0}^\infty x_{n-2}z^{-n+2}$$ as $z^{-1}(X(z)-x_0z^0)$ and $z^{-2}(X(z)-x_0z^0-x_1z^{-1})$, respectively:
$$z^{-1}(X(z)-x_0z^0)=z^{-1}\sum_{n\ge 1}x_nz^{-n}=z^{-1}\sum_{n\ge 0}x_{n+1}z^{-n+1}$$
and
$$z^{-2}(X(z)-x_0z^0-x_1z^{-1})=z^{-2}\sum_{n\ge 2}x_nz^{-n}=z^{-2}\sum_{n\ge 0}x_{n+2}z^{-n-2}\;.$$ 
In fact $$z^{-1}\sum_{n=0}^\infty x_{n-1}z^{-n+1}=z^{-1}\sum_{n=-1}^\infty x_nz^{-n}=z^{-1}(X(z)+x_{-1}z)=z^{-1}X(z)+1$$
and
$$z^{-2}\sum\limits_{n=0}^\infty x_{n-2}z^{-n+2}=z^{-2}\sum_{n=-2}^\infty x_nz^{-n}=z^{-2}\Big(X(z)+x_{-1}z+x_{-2}z^2\Big)=z^{-2}X(z)+\frac1z-1\;,$$
so $$z^{-1}\sum_{n=0}^\infty x_{n-1}z^{-n+1}+z^{-2}\sum\limits_{n=0}^\infty x_{n-2}z^{-n+2}=z^{-2}X(z)+z^{-1}X(z)+\frac1z\;.$$
Here $x_{-1}=1$ and $x_{-2}=-1$ are obtained by extrapolating the recurrence backwards.

I find it easiest to deal with the initial conditions by assuming that $x_n=0$ for all $n<0$ and using Iverson brackets to incorporate them in the recurrence. In this case the resulting recurrence is
$$x_n=x_{n-1}+x_{n-2}+[n=1]\;.\tag{1}$$
Now multiply $(1)$ through by $z^{-n}$ and sum over $n\ge 0$ to get $X(z)$:
$$\begin{align*}
X(z)&=\sum_{n\ge 0}x_{n-1}z^{-n}+\sum_{n\ge 0}x_{n-2}z^{-n}+\frac1z\\
&=\frac1zX(z)+\frac1{z^2}X(z)+\frac1z\;,
\end{align*}$$
so $z^2X(z)=zX(z)+X(z)+z$, and $$X(z)=\frac{z}{z^2-z-1}=\frac{z}{(z-\varphi)(z-\widehat\varphi)}\;,\tag{2}$$
where $\varphi=\frac12\left(1+\sqrt5\right)$ and $\widehat\varphi=\frac12\left(1-\sqrt5\right)$. Then $x_n=A(n)+B(n)$, where
$$A(n)=\lim_{z\to\varphi}\frac{z^n}{z-\widehat\varphi}=\frac{\varphi^n}{\varphi-\widehat\varphi}=\frac{\varphi^n}{\sqrt5}$$
and
$$B(n)=\lim_{z\to\widehat\varphi}\frac{z^n}{z-\varphi}=\frac{\widehat\varphi}{\widehat\varphi-\varphi}=-\frac{\widehat\varphi}{\sqrt5}\;,$$
i.e., $$x_n=\frac1{\sqrt5}\left(\varphi^n-\widehat\varphi^n\right)=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right)\;,$$
the familiar Binet formula.
Section 5.2.3 of this PDF has a brief discussion of the z-transform method with a couple of worked examples. The main difference is that the author prefers to compute the generating function and then make the substitution $z\mapsto\frac1z$; this has the virtue of avoiding negative exponents in the summations.
