# Homogeneous Case **Definition** A $k$-th order *linear homogeneous recurrence relation with constant coefficients* is a [[Recurrence Relation]] of the form: $x_{n} = \sum_{i=1}^{k} a_{i} \,x_{n-i}, \quad n \geq k, $satisfied by a [[Real sequences]] $(x_{n})_{n \geq 0}$ where $a_{i} \in \mathbb{R}$ for $i=1,\dots,k$. The sequence $(x_{n})_{n}$ is completely determined by $x_{0},x_{1},\dots,x_{k-1}$ (the initial condition). **In terms of matrices** Define the $k\times 1$ vector $\mathbf{v}_{n} = (x_{n+k-1},x_{n+k-2},\dots,x_{n})^{T}$. This new sequence satisfies the recurrence relation $\mathbf{v}_{n+1}=A\mathbf{v}_{n}$ for $n \geq 0$, where $A$ is a $k\times k$ matrix given by $A=\begin{pmatrix} a_{1} &a_{2} &a_{3} &\dots &a_{k-1} &a_{k} \\ 1 &0 &0 &\dots &0 &0 \\ 0 &1 &0 &\dots &0 &0 \\ 0 &0 &1 &\dots &0 &0 \\ \vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 0 &0 &0 &\ldots &1 &0 \end{pmatrix}$which we can prove by mathematical induction. It follows that $\mathbf{v}_{n}=A^{n}\mathbf{v}_{0}$ where $\mathbf{v}_{0}$ is the $n\times 1$ vector that contains the first $n$ values of the sequence. Note that $x_{n}= \mathbf{u} A^{n}\mathbf{v}_{0}$ where $\mathbf{u}$ is the $1\times n$ vector given by $\mathbf{u}=(0,0,\dots,1)$. E.g. the definition of a [[Fibonacci Sequence]] using matrices is given by $F_{n} = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ **Closed Formula** First we determine the [[Eigenpair|eigenvalues]] of $A$. The [[Characteristic polynomial of matrix]] is $P_{A}(\lambda)= \begin{vmatrix} \lambda-a_{1} &-a_{2} &-a_{3} &\dots &-a_{k-1} &-a_{k} \\ -1 &\lambda &0 &\dots &0 &0 \\ 0 &-1 &\lambda &\dots &0 &0 \\ 0 &0 &1 &\dots &0 &0 \\ \vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 0 &0 &0 &\ldots &-1 &\lambda \end{vmatrix}$When expanding by the first row it is easy to remark that all minors are triangular, so the determinant is equal to $\lambda^{k} -a_{1}\lambda^{k-1} -a_{2}\lambda^{k-2}-\dots-a_{k}$. The equation $P_{A}(\lambda)= \lambda^{k} -a_{1}\lambda^{k-1} -a_{2}\lambda^{k-2}-\dots-a_{k}=0$is called the *characteristic equation* (or *auxiliary equation*) of the linear recursive relation. Let $\lambda_{1},\lambda_{2},\dots,\lambda_{k}$ be the roots of the characteristic equation, which are, in fact, the eigenvalues of $A$. Depending on their multiplicities, we have to following possibilities: 1. If these roots are all distinct then $A$ is [[Diagonalisation of Square Matrix|diagonalizable]]. There exists an invertible matrix $S$ such that $A=SDS^-1$, where $D$ is diagonal with diagonal entries equal to the eigenvalues of $A$. From the equality $\mathbf{v}_{n}=SD^{n}S^{-1}\mathbf{v}_{0},$we conclude that the entries of $\mathbf{v}_{n}$ are linear combinations of $\lambda_{1}^{n}, \lambda_{2}^{n}, \dots,\lambda_{k}^{n}$. In particular, for $x_{n}$, which is the last coordinate of $\mathbf{v}_{n}$, there exists constants $\alpha_{1},\alpha_{2},\dots\alpha_{k}$ such that $x_{n}=\alpha_{1} \lambda_{1}^{n} + \alpha_{2} \lambda_{2}^{n} + \dots +\alpha_{k} \lambda_{k}^{n}, \quad \forall n\geq 0$The numbers $\alpha_{1},\alpha_{2},\dots\alpha_{k}$ are found from the initial condition by solving the linear system $\begin{align} \alpha_{1}+ \alpha_{2} +\dots +\alpha_{k} &= x_{0} \\ \alpha_{1} \lambda_{1} + \alpha_{2} \lambda_{2} +\dots +\alpha_{k} \lambda_{k} &= x_{1} \\ \alpha_{1} \lambda_{1}^{2} + \alpha_{2} \lambda_{2}^{2} +\dots + \alpha_{k}^{2} \lambda_{k}^{2} &= x_{2} \\ &\dots \\ \alpha_{1} \lambda_{1}^{k-1} + \alpha_{2} \lambda_{2}^{k-1} +\dots + \alpha_{k} \lambda_{k}^{k-1} &= x_{k-1} \end{align}$Note that the coefficient matrix is [[Vandermonde Matrix|Vandermonde]] so the linear system has a unique solution. 2. If the roots of the characteristic equation have multiplicities greater than 1, it might happen that $A$ is not diagonalizable. The [[Jordan Canonical Form]] of $A$ has blocks ... # Inhomogeneous Case **Definition** A $k$-th order *linear inhomogeneous recurrence relation with constant coefficients* has the form: $x_{n} =f(n) + \sum_{i=1}^{k} a_{i} \,x_{n-i}, \quad n \geq k$ **Position to Term Formula** As is the case with [[Ordinary Differential Equation|ODEs]], to find the general term of an inhomogeneous linear recurrence, one has to find a particular solution to the recurrence, then add to it the general term of the associated homogeneous recurrence relation A linear recurrence relation may be solved using a [[Ordinary Generating Function]]. # Examples # Reference(s) - [[@gelcaPutnam2007]].