<s>[INST] 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?
 [/INST] 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.
</s>