From a Recurrence to a State Vector
A recurrence specifies each new term of a sequence using earlier terms. To use matrix methods on it, collect enough consecutive terms into one vector so that one matrix multiplication advances the sequence by one index. The resulting system is first-order in the state vector, even when the original recurrence refers to several earlier terms.
Throughout, let the sequence be real-valued and let its coefficients be real. When discussing eigenvalues or roots, we allow complex scalars as well, since a real matrix can have complex eigenvalues. Consider a recurrence of order \(m\), where \(m\geq 1\), in the normalized form
The coefficients \(a_0,\dots,a_{m-1}\) are fixed. The recurrence together with \(m\) initial values \(x_0,\dots,x_{m-1}\) determines the sequence. If a recurrence is initially written with a nonzero coefficient on \(x_{n+m}\), divide through by that coefficient to obtain this form.
The first \(m-1\) rows shift the entries of the state forward by one position. The last row uses the recurrence to calculate the new term. This construction turns a recurrence with memory into a one-step matrix update.
Proof. Write \(\mathbf{y}_n=(x_n,x_{n+1},\dots,x_{n+m-1})^{\top}\). Multiplication by the first \(m-1\) rows of \(\mathbf{C}\) gives \(x_{n+1},x_{n+2},\dots,x_{n+m-1}\) in that order. The last row gives \(a_0x_n+a_1x_{n+1}+\cdots+a_{m-1}x_{n+m-1}=x_{n+m}\), by the recurrence. These are exactly the entries of \(\mathbf{y}_{n+1}\). Conversely, the first \(m-1\) rows of any equation \(\mathbf{y}_{n+1}=\mathbf{C}\mathbf{y}_n\) force each state’s entries to shift in this way, and the last row forces the recurrence. Given \(\mathbf{y}_0\), the matrix equation determines each next state uniquely; its entries therefore give the unique sequence with the specified initial values. When \(m=1\), there are no shift rows, and the single update \(x_{n+1}=a_0x_n\) is precisely the recurrence. \(\square\)
In particular, if \(\mathbf{e}_1=(1,0,\dots,0)^{\top}\), then the sequence term \(x_n\) is the first coordinate of the \(n\)th state: \(\ x_n=\mathbf{e}_1^{\top}\mathbf{y}_n=\mathbf{e}_1^{\top}\mathbf{C}^{n}\mathbf{y}_0.\) This expresses the scalar sequence through matrix powers, while retaining its initial values in \(\mathbf{y}_0\).
Characteristic Roots and Matrix Eigenvalues
A standard way to find candidate exponential patterns in a recurrence is to substitute \(x_n=r^n\). For a nonzero \(r\), the substitution gives \(r^{n+m}=a_0r^n+\cdots+a_{m-1}r^{n+m-1}\). Dividing by \(r^n\) yields the polynomial equation below. Its roots are called the characteristic roots of the recurrence.
The polynomial also records the condition for the exponential pattern at \(r=0\), even though division by \(r^n\) was used to motivate it only for nonzero \(r\). The exact link between these roots and the companion matrix follows from its eigenvector equations.
Proof. First suppose \(\lambda\) is an eigenvalue, so there is a nonzero vector \(\mathbf{v}=(v_1,\dots,v_m)^{\top}\) satisfying \(\mathbf{C}\mathbf{v}=\lambda\mathbf{v}\). The first \(m-1\) rows give \(v_{j+1}=\lambda v_j\) for \(1\leq j<m\). If \(v_1=0\), these equations successively give \(v_2=0,\dots,v_m=0\), contradicting that \(\mathbf{v}\) is nonzero. Thus \(v_1\ne0\), and the same equations give \(v_j=\lambda^{j-1}v_1\). The last row now gives $$ a_0v_1+a_1\lambda v_1+\cdots+a_{m-1}\lambda^{m-1}v_1 =\lambda v_m=\lambda^m v_1. $$ Dividing by \(v_1\ne0\) gives \(q(\lambda)=0\). For \(m=1\), the first-row equations are absent, but a nonzero eigenvector has \(v_1\ne0\) and the last-row equation gives \(a_0v_1=\lambda v_1\), again yielding \(q(\lambda)=0\). Conversely, suppose \(q(\lambda)=0\). Set \(\mathbf{v}=(1,\lambda,\dots,\lambda^{m-1})^{\top}\), which is nonzero. The first \(m-1\) entries of \(\mathbf{C}\mathbf{v}\) are \(\lambda,\dots,\lambda^{m-1}\). Its last entry is \(a_0+a_1\lambda+\cdots+a_{m-1}\lambda^{m-1}=\lambda^m\), by \(q(\lambda)=0\). Therefore \(\mathbf{C}\mathbf{v}=\lambda\mathbf{v}\), so \(\lambda\) is an eigenvalue. For \(m=1\), the same vector is \((1)\), and the last-entry equation is \(a_0=\lambda\). \(\square\)
The proof gives a useful form for an eigenvector associated with a characteristic root: \((1,\lambda,\dots,\lambda^{m-1})^{\top}\). The result identifies the eigenvalues and roots; it does not say that eigenvectors alone specify the sequence, since the initial state also matters.
Worked Recurrences
Worked Example: A Second-Order Recurrence with Two Roots
Write \(x_{n+2}=3x_{n+1}-2x_n\), with \(x_0=1\) and \(x_1=2\), as a matrix system. Find its characteristic roots and check the first two updates.
Here \(m=2\), \(a_0=-2\), and \(a_1=3\). The state and companion matrix are
Multiplying gives the next state:
Thus \(x_2=4\), which agrees with \(3x_1-2x_0=3\cdot2-2\cdot1=4\). The following update is
Again the recurrence gives \(x_3=3x_2-2x_1=3\cdot4-2\cdot2=8\), matching the matrix update. The characteristic polynomial is \(q(r)=r^2-3r+2=(r-1)(r-2)\), so the roots are \(1\) and \(2\). They are eigenvalues of \(\mathbf{C}\); for instance, \(\mathbf{C}(1,1)^{\top}=(1,1)^{\top}\), and \(\mathbf{C}(1,2)^{\top}=(2,4)^{\top}=2(1,2)^{\top}\).
Worked Example: A Third-Order Recurrence
For \(x_{n+3}=2x_{n+2}+x_{n+1}-2x_n\), take initial values \(x_0=1\), \(x_1=0\), \(x_2=1\). Form the system, calculate two updates, and identify the characteristic roots.
The coefficients are \(a_0=-2\), \(a_1=1\), and \(a_2=2\). Hence
The first update, with each row product shown, is
This says \(x_3=0\), and the recurrence gives \(2x_2+x_1-2x_0=2\cdot1+0-2\cdot1=0\). The next update is
In scalar terms, \(x_4=2x_3+x_2-2x_1=2\cdot0+1-0=1\), so this update also agrees. The characteristic polynomial is \(q(r)=r^3-2r^2-r+2=(r-1)(r-2)(r+1)\). Thus the roots are \(1,2,-1\). The theorem predicts each is an eigenvalue; for \(\lambda=-1\), for example, \(\mathbf{C}(1,-1,1)^{\top}=(-1,1,-1)^{\top}=-1(1,-1,1)^{\top}\).
Worked Example: A Repeated Characteristic Root
Consider \(x_{n+2}=2x_{n+1}-x_n\), with \(x_0=2\) and \(x_1=5\). Convert it to a matrix system and check its first two generated terms.
The coefficients are \(a_0=-1\) and \(a_1=2\), so
The first update is
The recurrence gives \(x_2=2x_1-x_0=2\cdot5-2=8\). Updating once more gives
Indeed, \(x_3=2x_2-x_1=2\cdot8-5=11\). The characteristic polynomial is \(q(r)=r^2-2r+1=(r-1)^2\), so \(1\) is a repeated characteristic root and, by the theorem, an eigenvalue of \(\mathbf{C}\). Directly, \(\mathbf{C}(1,1)^{\top}=(1,1)^{\top}\). This example illustrates that the root-to-eigenvalue statement applies whether or not a root is repeated.
A Common Coefficient-Order Mistake
The state-vector order determines the order of the coefficients in the last row. For the recurrence \(x_{n+2}=3x_{n+1}-2x_n\), the state is \((x_n,x_{n+1})^{\top}\), so the last row must apply \(-2\) to \(x_n\) and \(3\) to \(x_{n+1}\). Reversing those coefficients gives the wrong update:
This predicts \(x_2=-1\), but the recurrence requires \(x_2=3\cdot2-2\cdot1=4\). With the coefficients in the correct order, the calculation is
A reliable check is to multiply the last row by the state vector and confirm that it reproduces the recurrence’s right-hand side exactly. The first rows should shift the existing terms in the same order used to define the state.
Why the Matrix Form Is Useful
Once a recurrence is written as \(\mathbf{y}_{n+1}=\mathbf{C}\mathbf{y}_n\), the state after \(n\) steps is \(\mathbf{y}_n=\mathbf{C}^n\mathbf{y}_0\). The companion-matrix theorem identifies the eigenvalues relevant to this iteration directly from the scalar recurrence’s characteristic polynomial. Thus methods for studying matrix powers can be applied to recurrence sequences, with the initial values represented by the initial state.
The state convention is part of the model, not just notation: changing the order of entries changes the displayed matrix and requires the rows to be adjusted accordingly. Keeping the fixed order \((x_n,\dots,x_{n+m-1})^{\top}\) makes the shift rows and coefficient row systematic. It also makes the connection between a recurrence and its characteristic roots precise, including when roots repeat.
Check Your Understanding
Use the state order \((x_n,\dots,x_{n+m-1})^{\top}\) in each question.
- Write the companion matrix for \(x_{n+2}=4x_{n+1}+x_n\), and state its characteristic polynomial.
- For \(x_{n+3}=x_{n+2}-2x_n\), write the state vector and companion matrix.
- Prove directly from the eigenvector equations that any eigenvalue of a companion matrix is a root of its recurrence’s characteristic polynomial.
- For \(x_{n+2}=2x_{n+1}-x_n\), verify that \((1,1)^{\top}\) is an eigenvector and identify its eigenvalue.
- A student uses the last row \((a_{m-1},\dots,a_0)\). Explain why this does not match the stated state convention.
