7
$\begingroup$

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.

  • 0
    @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.2012-08-26

1 Answers 1

6

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

  • 0
    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.2012-08-19