# Solving Linear Recurrences

Posted on January 10, 2017
Tags: math

$$\newcommand{\R}{\mathbf{R}}$$ In this post, we consider finding “closed-form” formulas for linear recurrences of the shape

\begin{equation} \label{eq:1} x_{n+1} = A x_n, \quad \text{for $n\geq0$ with $x_0$ given}. \end{equation}

Here, $$\{ x_{0}, x_1, x_2, \dots \} \subseteq \R^p$$ and $$A$$ is a $$(p \times p)$$ matrix.

To obtain a formula for $$x_n$$, decompose $$A$$ into its Jordan Normal Form, so that

\begin{equation} \label{eq:2} A = P^{-1} J P, \quad \text{where} \quad J = \begin{bmatrix} J_1 \\ & J_2 \\ & & \dots \\ & & & J_q \end{bmatrix} \text{ is a Jordan matrix with blocks $J_1, \dots, J_q$.} \end{equation}

Define $$y_n = Px_n$$, so that (\ref{eq:1}) reads

\begin{equation} \label{eq:3} y_{n+1} = J y_n = \begin{bmatrix} J_1 \\ & J_2 \\ & & \dots \\ & & & J_q \end{bmatrix} y_n \end{equation}

Clearly, we may analyze the components of $$y_n$$ corresponding to $$J_1, \dots, J_q$$ separately, so that the general case reduces to solving the linear recurrence

\begin{equation} \label{eq:4} z_{n+1} = \begin{bmatrix} \lambda & 1 \\ & \lambda & 1 \\ & & \dots & \dots \\ & & & \lambda & 1\\ & & & & \lambda\\ \end{bmatrix} z_n \end{equation}

Proposition. The solution to (\ref{eq:4}) when $$z_n = (z_n^{(1)}, \dots, z_n^{(m)})^{\intercal} \in \R^m$$ is given by

\begin{equation} \label{eq:5} z_n^{(k)} = \sum_{j=0}^{m-k} \binom{n}{j} \lambda^{n-j} z_0^{(k+j)}, \qquad k = 1, 2, \dots, m. \end{equation}

In particular,

\begin{equation} \label{eq:6} z_n^{(k)} = \lambda^n f_k(n), \qquad \text{where $f_k$ is a polynomial of degree $m-k$.} \end{equation}

Proof. Using induction on $$m$$ it suffices to prove the claim only for $$k = 1$$, which is a simple calculation.

Example. Consider the recurrence relation

\begin{equation} \label{eq:7} x_{n+p} = A_0 x_n + \dots + A_{p-1} x_{n + (p-1)}, \qquad n \geq0 \end{equation}

with $$x_0, \dots, x_{p-1}$$ given. Set $$z_n = (x_{n+(p-1)}, \dots, x_n)^{\intercal}$$ to transform (\ref{eq:7}) into (\ref{eq:1})

\begin{equation} \label{eq:8} z_{n+1} = A z_n \quad \text{where} \quad A = \begin{bmatrix} A_{p-1} & A_{p-2} & \dots & \dots & A_0 \\ 0 & 1 & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} \end{equation}

It is well known that $$A$$ has a Jordan block decomposition of the shape

\begin{equation} \label{eq:9} A = P^{-1} \{ J_1(\lambda_{1}; m_1) \oplus \dots \oplus J_r(\lambda_{r}; m_r)\} P \end{equation}

where $$J(\lambda;m)$$ is a size $$m$$ Jordan block with eigenvalue $$\lambda$$ and where $$\lambda_1, \dots, \lambda_r$$ and $$m_1, \dots, m_r$$ are the distinct roots and corresponding multiplicities of the characteristic polynomial of $$A$$

\begin{equation} \label{eq:10} \chi_{A}(x) = \pm(x^p - A_{p-1} x^{p-1} - \dots - A_0) = \pm (x-\lambda_1)^{m_1} \dots (x-\lambda_r)^{m_r}. \end{equation}

Now the Proposition above is easily seen to imply that

\begin{equation} \label{eq:11} x_n = \sum_{j=1}^r \lambda_j^n \cdot f_j(n) \qquad \text{where $f_j(n)$ are polynomials of degree $m_j -1$.} \end{equation}

By finding the sufficiently many terms of $$x_0, x_1, \dots$$ one can solve for the coefficients of $$f_j(n)$$.