Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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}=$$





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}=$$


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|cite|improve this question
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
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}$$


$$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$$


$$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


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




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|cite|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

Your Answer


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.