# 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.

-
It's probably easier to rewrite the equation as $x[n + 2] = x[n + 1] + x[n]$, and apply the formulas $Z(x_{n+1}) = zX(z) - zx_0$ and $Z(x_{n+2}) = z^2X(n) - z^2x_0 - zx_1$. – Bitrex Aug 19 '12 at 8:23
@Bitrex I wasn't quite sure on the formula for the one-sided transform, so I tried to derive it myself more or less. And it looks like you're right on rewriting the equation. – Mike Aug 26 '12 at 20:42

(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.

-
Oops! I did $n=i+1$ instead of $i=n+1$. So I have too many terms, not too few. I'll take a closer look at the rest later. – Mike Aug 19 '12 at 17:55