Solving Linear Recurrences
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)\).