# Solving for the closed form of recurrence relations using characteristic polynomial

I know how to find the closed form of some recurrence relations such as those that are similar to the Fibonacci Sequence. I am not sure how to solve a recurrence relation using the characteristic polynomial when there is a constant involved like

$$a_n = 3a_{n-1} -1$$ (I know how to solve this using substitution, but I want to know-how using the characteristic polynomial)

or

$$a_n = 6a_{n-1} + 7a_{n-2} +3$$

In using the characteristic polynomial, how do I treat the constant when factoring?

## 1 Answer

There is always the matrix approach: $$\begin{pmatrix} a_{n} \\ 1 \end{pmatrix} = \begin{pmatrix} 3 & -1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ 1 \end{pmatrix}$$ The characteristic polynomial of that matrix is $$x^2-4x+3=(x - 3)(x - 1)$$ and so $$a_n=\alpha 3^n + \beta 1^n$$. The coefficients are determined by the initial conditions.

The same approach works for the other recurrence: $$\begin{pmatrix} a_{n} \\ a_{n-1} \\ 1 \end{pmatrix} = \begin{pmatrix} 6 & 7 & 3 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ a_{n-2} \\ 1 \end{pmatrix}$$ The characteristic polynomial of that matrix is $$x^3-7x^2-x+7=(x - 7) (x + 1) (x - 1)$$ and so $$a_n=\alpha 7^n + \beta (-1)^n + \gamma 1^n$$. The coefficients are determined by the initial conditions.

The characteristic polynomial of $$a_n = 6a_{n-1} + 7a_{n-2} +3$$ is $$(x - 7) (x + 1)$$ and appears as a factor in the characteristic polynomial of the matrix, as in the first example.

• I have not really studied matrices yet, but thanks1! – SuperMage1 Jan 8 '20 at 12:19
• @SuperMage1, it's an opportunity and motivation to learn about matrices in this context. – lhf Jan 8 '20 at 17:41