Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
