2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have not really studied matrices yet, but thanks1! $\endgroup$ – SuperMage1 Jan 8 at 12:19
  • 1
    $\begingroup$ @SuperMage1, it's an opportunity and motivation to learn about matrices in this context. $\endgroup$ – lhf Jan 8 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.