Characteristic equation. What is it?

Question

Consider a recursive equation: $$ a_n = A a_ {n-1} + Ba_ {n-2} $$ And for this type of equation, there is characteristic equation: $ x ^ 2 = Ax + B $. What does exactly means that this equation is characteristic? These equations are based on a recursive for each or only for a form as above? What is the characteristic equation?

Answer 1

It's just a name, don't look too much into names of mathematical objects.

The equation originates from this simple observation: suppose a geometric sequence $1,x,x^2,\dots,x^n$ (with $x\ne0$) solves the given recurrence; then we must have, for $n\ge 2$, $$ x^n=Ax^{n-1}+Bx^{n-2} $$ and, removing the common factor $x^{n-2}$, we get $$ x^2=Ax+B=0 $$

If $x$ is a solution to this equation, then the geometric sequence is indeed a solution for the recurrence. If $x_1$ and $x_2$ are distinct solutions of the characteristic equation, then also $$ a_n=\alpha x_1^n+\beta x_2^n $$ is a solution for the recurrence. Since we have found a two parameter family of solutions, these are all solutions.

In case the characteristic equation has just one root $x_0$ (zero discriminant, two coincident roots, if you prefer), then it can be shown that the complete set of solutions of the recurrence is $$ a_n=\alpha x_0^n+ n\beta x_0^n $$

Note that also complex roots should be considered.

This can be generalized to any linear recurrence equation with constant coefficients.

---

Why does one look for geometric sequences as solutions? Because they're the simplest ones after arithmetic sequences and because, in this case, they work. ;-) There are better justifications, I know, but they would require too long arguments for an answer here.

Secondly, the set of solutions of a linear recurrence forms a vector space; if the sequences $(r_n)$ and $(s_n)$ are solutions of $a_n=Aa_{n-1}+Ba_{n-2}$ then so is the sequence $n\mapsto \alpha r_n+\beta r_n$, for all (complex) numbers $\alpha$ and $\beta$. But, since a solution is determined once you fix the terms $a_0$ and $a_1$, you have that this vector space has dimension $2$. In particular, once you find two linearly independent solutions, then they form a basis of this vector space.

If the characteristic equation has distinct solutions $x_1$ and $x_2$, then the geometric sequences built from them are linearly independent: suppose $$ \alpha x_1^n + \beta x_2^n = 0 $$ for all $n$; then you have (using $n=0$ and $n=1$) $$ \begin{cases} \alpha + \beta=0\\ \alpha x_1+\beta x_2=0 \end{cases} $$ and $$ \det\begin{bmatrix}1 & 1 \\ x_1 & x_2\end{bmatrix}=x_2-x_1\ne0 $$ so $\alpha=\beta=0$.

If the characteristic equation has a double root $x_0$, then it is easy to see that the sequences $(x_0^n)$ and $(nx_0^n)$ are solutions and, again, from $$ \alpha x_0^n + \beta nx_0^n=0 $$ for all $n$, you get (using $n=0$ and $n=1$) $$ \begin{cases} \alpha = 0 \\ \alpha x_0+\beta x_0 \end{cases} $$ that entails $\alpha=\beta=0$.

Why is $(nx_0^n)$ a solution? Note that $(x_0^n)$ is a solution because $x_0$ is a root. The condition in this case says that if we set $A=2C$, then $B=-C^2$ and $x_0=C$, so we can write the equation as $a_n=2Ca_{n-1}+C^2a_{n-2}$. Now, in the special case where $a_n=nx_0^n$ we have \begin{align} 2C(n-1)x_0^{n-1}-C^2(n-2)x_0^{n-2} &=x_0^{n-2}(2C(n-1)x_0-C^2(n-2))\\ &=x_0^{n-2}(2x_0^2(n-1)-x_0^2(n-2)\\ &=x_0^{n}(2n-2-n+2)\\ &=nx_0^n \end{align} that is, $$ nx_0^n=A(n-1)x_0^{n-1}+B(n-2)x_0^{n-2}. $$

Note that in the recurrence equation you can assume $B\ne0$ or it would be easier to solve.

Hence also in this case we found two linearly independent solutions and so they form a basis of the solution set.

Added note

Consider the set $V$ consisting of all sequences $r=(r_n)$, that is, all maps $\mathbb{N}\to\mathbb{C}$. We can define addition of $r=(r_n)$ and $s=(s_n)$ by decreeing that $r+s$ is the map $n\mapsto r_n+s_n$. In other words, sequences are summed term by term. Multiplication by scalars is similar: $\alpha r$ is the map $n\mapsto \alpha r_n$ (every term is multiplied by $\alpha$).

Verifying that these operations make $V$ into a vector space is standard.

The set of solutions of a linear recurrence (not only of degree $2$) is a subspace: indeed, if $r$ and $s$ are solutions, then also $\alpha r+\beta s$ is a solution. For the given equation this amounts to verifying that $$ (\alpha r_n+\beta s_n)=A(\alpha r_{n-1}+\beta s_{n-1})+B(\alpha r_{n-2}+\beta s_{n-2}) $$ for all $n$, once we know that $$ r_n=Ar_{n-1}Br_{n-2}\qquad\text{and}\qquad s_n=As_{n-1}Bs_{n-2} $$ for all $n$. It's the same for general linear recurrences.

Since the solution of a degree $k$ linear recurrence is determined once we know its first $k$ terms, the subspace of solutions has dimension $k$ (fix a proof for this). In the case of degree $2$ just two linearly independent solutions give a basis.

Answer 2

The characteristic equation (or auxiliary equation) is an algebraic equation of degree $n$ on which depends the solutions of a given $n$th-order differential equation or the solution of a recursive sequence. The characteristic equation can only be formed when the differential equation (recursive sequence) is linear, homogeneous, and has constant coefficients.

The characteristic equation for the above sequence is what you've written.