# How to get the characteristic equation?

In my book, this succession defined by recurrence is presented:

$$U_n=3U_{n-1}-U_{n-3}$$

And it says that the characteristic equation of such is:

$$x^3=3x^2-1$$

Honestly, I don't understand how. How do I get the characteristic equation given a succession?

-
Put $U_n=x^n$ in your original equation. – Artem Jul 4 '12 at 20:26
^ and then factor out the common powers of $x.$ – user2468 Jul 4 '12 at 20:27
You can take a route via generation functions - which shows why it all works. Or you can see that you have a linear equation which is defined by specifying two values, and see that the quadratic gives you two linearly independent functions, and therefore the procedure works. Generating function technology deals with exceptional cases rather better. – Mark Bennet Jul 4 '12 at 21:03

$$U_n=3U_{n-1}-U_{n-3}$$

Convert each subscript to an exponent:

$$U^n=3U^{n-1}-U^{n-3}$$

Change the variable to the one that you want to use in the characteristic equation:

$$x^n=3x^{n-1}-x^{n-3}$$

Divide through by the smallest exponent, in this case $n-3$:

$$x^{n-(n-3)}=3x^{(n-1)-(n-3)}-1\;,$$

which simplifies to $$x^3=3x^2-1\;.$$

With a little practice you can do the conversion in one go. For instance, the recurrence $$a_n=4a_{n-2}-6a_{n-3}+3a_{n-4}$$ has characteristic equation $$x^4=4x^2-6x+3\;,$$ as you can check by following through the steps given above.

-

Often one sees much handwaving here: rote rules, guesses, etc. But the conceptual background is very simple. Let $\rm\,S\,$ be the linear shift operator $\rm\:S\, U_n = U_{n+1}.\,$ In operator form we have

$$\rm 0 = U_{n+3} - 3\, U_{n+2} + U_n = S^3 U_n - 3\, S^2 U_n + U_n = (S^3 - 3\,S^2 + 1)\, U_n = f(S)\, U_n$$

Factoring $\rm\,f(S) = (S-c_1)\,(S-c_2)\,(S-c_2),\,$ for $\rm\, c_i\in \mathbb C,\,$ reduces to solving linear recurrences $\rm\: (S-c)\,U_n = 0,\:$ i.e. $\rm\,U_{n+1} = c\,U_n,\,$ so $\rm\:U_n = U_o c^n.\,$ Because the $\rm\,c_i,\:$ are independent of $\rm\,n\,$ the operators $\rm\, S-c_i\:$ commute, so if the roots $\rm\,c_i\,$ are distinct, this yields three solutions $\rm\,c_i^n.\,$ Simple linear algebra (using the Casoratian) shows that these three solutions span the solution space.

Thus the characteristic polynomial is simply the polynomial $\rm\,f(S)\,$ obtained from writing the recurrence in operator form, and the form of the solutions follows immediately from factoring the characteristic polynomial, which reduces the solution of an $\rm\,n$-th order constant coefficient recurrence to the solution of $\rm\,n\,$ first-order constant coefficient recurrences.

-

Given a recurrence, $$a_{n+j+1} = \sum_{k=0}^{j} c_k a_{n+k}$$ Take $a_n = x^n$. Then the characteristic equation is $$x^{n+j+1} = \sum_{k=0}^{j} c_k x^{n+k}$$ which gives us the characteristic equation $$x^{j+1} - \sum_{k=0}^{j} c_k x^k = 0$$ This is analogous to taking $y = e^{mx}$ when we solve linear differential equations.

-

"Guess" that $U(n) = x^n$ is a solution and plug into the recurrence relation:

$$x^n = 3x^{n-1} - x^{n-3}$$

Divide both sides by $x^{n-3}$, assuming $x \ne 0$:

$$x^3 = 3x^2 - 1$$

Which is the characteristic equation you have.

-