How to Solve a Recurrence Relation Using the Z-Transform

A Z-transform can turn a linear recurrence into an algebraic equation, making it easier to solve for the sequence. The key detail is to use the unilateral Z-transform when the sequence is defined from an initial index such as $n=0$: its shift rules explicitly carry the initial values into the calculation.

This method works especially well for linear recurrences with constant coefficients. You will transform the recurrence, solve for the transform, and then identify the sequence from standard transform pairs.

The unilateral Z-transform

For a sequence $x_0,x_1,x_2,\ldots$, define its unilateral Z-transform by

$$X(z)=\sum_{n=0}^{\infty}x_n z^{-n}.$$

The shift formulas you need include the starting values:

$$\mathcal{Z}\{x_{n+1}\}=z\bigl(X(z)-x_0\bigr),$$ $$\mathcal{Z}\{x_{n+2}\}=z^2X(z)-z^2x_0-zx_1.$$

More generally, shifting a sequence forward introduces terms involving its initial values. This is why the unilateral transform is convenient for initial-value recurrences: the starting conditions are built into the transformed equation.

A step-by-step method

Suppose a recurrence is given for $n\ge 0$, along with enough initial values to determine its solution.

1. Write the transform. Set $X(z)=\mathcal{Z}\{x_n\}$ using the unilateral convention.
2. Transform each term. Use the appropriate shift formula, substituting the given initial values.
3. Solve algebraically. Collect the terms involving $X(z)$ and isolate it.
4. Invert the result. Factor the denominator and use standard transform pairs or partial fractions.
5. Check the first terms. Substitute them into the recurrence and compare with the initial values.

For a nonhomogeneous recurrence, transform the forcing sequence as well. The resulting equation is still algebraic in $X(z)$, provided the forcing transform is known or can be calculated.

Worked example

Solve

$$x_{n+2}-3x_{n+1}+2x_n=0,\qquad x_0=1,\quad x_1=4.$$

Let $X(z)=\mathcal{Z}\{x_n\}$. Apply the shift rules to each term:

$$\bigl(z^2X(z)-z^2x_0-zx_1\bigr)-3z\bigl(X(z)-x_0\bigr)+2X(z)=0.$$

Substitute $x_0=1$ and $x_1=4$:

$$z^2X(z)-z^2-4z-3zX(z)+3z+2X(z)=0.$$

Collect the transform terms and the remaining terms:

$$(z^2-3z+2)X(z)=z^2+z.$$

Therefore,

$$X(z)=\frac{z^2+z}{(z-1)(z-2)}.$$

To use standard unilateral Z-transform pairs, write this in terms of $z/(z-a)$:

$$X(z)=-2\frac{z}{z-1}+3\frac{z}{z-2}.$$

Since $\mathcal{Z}\{a^n\}=z/(z-a)$, the inverse transform gives

$$x_n=-2\cdot 1^n+3\cdot 2^n=-2+3\cdot 2^n,\qquad n\ge 0.$$

Check the initial terms: $x_0=-2+3=1$ and $x_1=-2+6=4$. The recurrence also holds: substituting $x_n=-2+3\cdot 2^n$ makes its left side zero for every $n\ge 0$.

Convergence and transform conventions

The transform pair $\mathcal{Z}\{a^n\}=z/(z-a)$ is valid in the region $|z|>|a|$ for the unilateral transform of a right-sided sequence. In the example, the sequence contains a $2^n$ term, so the series defining its transform converges for $|z|>2$. In many recurrence exercises, you can manipulate the transform as a formal power series and focus on recovering its coefficients; the convergence region matters when interpreting it as an analytic function.

A bilateral Z-transform sums over all integer indices, while the unilateral transform starts at $n=0$. Their shift formulas differ. Do not apply a bilateral shift rule to a recurrence with specified initial values unless you have deliberately chosen that convention and accounted for the starting boundary.

Common mistakes

• Dropping initial-value terms. For example, $\mathcal{Z}\{x_{n+1}\}$ is $z(X(z)-x_0)$, not simply $zX(z)$.
• Using the wrong transform convention. State whether the sum starts at $n=0$ or runs over all integers before applying shift rules.
• Mixing up the inverse pair. With this convention, $a^n$ corresponds to $z/(z-a)$, not $1/(z-a)$.
• Stopping before checking. Verify that the recovered sequence gives the specified initial values and satisfies the recurrence.
• Assuming every recurrence needs a transform. For a short homogeneous recurrence, a characteristic equation may be quicker. The Z-transform is particularly useful when initial conditions or forcing terms need systematic handling.

The same procedure applies to higher-order linear recurrences: use the shift formula for each order, include every required initial value, then solve and invert the resulting rational function.