Solving linear difference equations by the Z-transform

Definition

Let $k \ge 1$, let $a_0, \ldots, a_k$ be complex numbers with $a_0 \ne 0$, let $(f_n)_{n \ge 0}$ be a sequence with a unilateral Z-transform $F$, and let $c_0, \ldots, c_{k-1}$ be complex numbers. Consider the linear recurrence with constant coefficients $$a_0 y_{n+k} + a_1 y_{n+k-1} + \cdots + a_k y_n = f_n \quad (n \ge 0), \qquad y_j = c_j \ (0 \le j < k).$$ The Z-transform method solves it in three steps.

1. Apply the unilateral Z-transform and the shift property, $\mathcal{Z}\{(y_{n+m})_{n \ge 0}\} = z^m \left( Y(z) - \sum_{j<m} y_j z^{-j} \right)$, to get $P(z) Y(z) = F(z) + Q(z)$, where $P(z) = \sum_{m=0}^{k} a_{k-m} z^m$ and $Q$ is a polynomial built from $c_0, \ldots, c_{k-1}$.
2. Solve: $Y(z) = (F(z) + Q(z)) / P(z)$.
3. Recover $(y_n)$ from $Y$ by the inverse Z-transform, in practice by a partial fraction decomposition and known transform pairs.