Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.