Finding General Terms for First- and Second-Order Linear Recurrences

I learned it here Recently I've been quite busy. Although I had written this set of problems before, I hadn't studied it carefully. Then, in order to explain the problems without embarrassment, I dragged GJY into researching this until two or three in the morning. Actually, if one has learned characteristic roots, this problem is easy to see, but I hadn't learned it. After asking many experts, I finally found the direction of characteristic roots. Since it was really late, I had to log off in shame. The next morning, after spending a dozen minutes reading, I suddenly understood and marveled at how simple it was (not really). The computation is simple, but the construction is challenging. Fortunately, this is a general solution; use it a few times and you'll remember it. Characteristic roots seem to be content from linear algebra (really, it seems).

A little supplement written at the beginning: In this article, because geometric sequences are easier to find the nth term, we hope to transform a recurrence into a geometric sequence form. Here, I first give the recurrence and the geometric sequence, then try to establish a connection between them (equivalence relations between variables).

1. First-order

Of the form:

$$x_n = px_{n-1} + q \qquad (a)$$

When $p=1$, this is an arithmetic sequence. When $p\neq1$, consider constructing a geometric sequence (this is a general construction): $$x_{n+1}-x_0=p(x_n-x_0) \qquad (b)$$

Here, each term is of the form $x_i-x_0$, so it becomes a geometric sequence with common ratio $p$.

We consider transforming $(b)$ into the form of $(a)$, so that we can establish connections between the variables.

$$\begin{aligned} x_{n+1}&=px_n-px_0+x_0 \\ x_{n+1}&=px_n+(1-p)x_0 \qquad (b') \end{aligned}$$

Now we can clearly see the shape of $(a)$ in $(b')$. Further, we establish connections between variables.

$$q=(1-p)x_0 \newline x_0=\frac{q}{1-p}$$

At this point, we have obtained all constants $p,x_0$ of the geometric sequence $b$, and we can find any term $x_n-x_0$, and thus any term $x_n$.

So $x_n=(x_1-x_0)p^{n-1}+x_0$.

2. Second-order

$$x_n=px_{n-1}+qx_{n-2} \qquad (a)$$

This is a second-order linear recurrence. Why is it second-order? Probably because it uses two $x$'s.

Similar to the first-order recurrence, we hope to construct a geometric sequence (again, this is a general construction):

$$x_{n+1}-ax_n=b(x_n-ax_{n-1}) \qquad (b)$$

Here, each term is of the form $x_i-ax_{i-1}$, very similar to the approach in $1.(b)$.

Similarly, we try to transform it into the form of $(a)$.

$$x_{n+1}-ax_n=bx_n-abx_{n-1} \newline x_{n+1}=(a+b)x_n-abx_{n-1} \qquad (b')$$

Then comparing $(a)$ and $(b')$ we get:

$$\left\{ \begin{aligned} a+b&=p \\ ab&=-q \end{aligned} \right.$$

To solve for $a,b$, we consider constructing a quadratic equation with roots $a,b$. Using Vieta's formulas:

$$x^2-px-q=0$$

This equation is called the characteristic equation of the sequence, and $a,b$ are called the characteristic roots.

Since $a,b$ are the two roots of the equation, they are "symmetric"; consider the symmetry of the function graph.

Returning to equation $(b)$, because they are symmetric, we can obtain two geometric sequences:

$$\left\{ \begin{aligned} x_{n+1}-ax_n&=b(x_n-ax_{n-1}) \\ x_{n+1}-bx_n&=a(x_n-bx_{n-1}) \end{aligned} \right.$$

The right-hand sides can be simplified:

$$\left\{ \begin{aligned} x_{n+1}-ax_n&=b^{n-1}(x_2-ax_1) \\ x_{n+1}-bx_n&=a^{n-1}(x_2-bx_1) \end{aligned} \right.$$

To find $x_n$, subtract them to eliminate $x_{n+1}$ on the left:

$$(a-b)x_n=a^{n-1}(x_2-bx_1)-b^{n-1}(x_2-ax_1) \newline x_n=\frac{a^{n-1}(x_2-bx_1)-b^{n-1}(x_2-ax_1)}{a-b} \qquad (c)$$

2.1 Example:

$$x_0=1,x_1=3,x_n=2x_{n-1}+2x_{n-2}$$

Now we know our goal is to find $a,b$. Directly solve the characteristic equation $x^2-(2)x-(2)=0$ to get:

$$\left\{ \begin{aligned} a&=1+\sqrt{3} \\ b&=1-\sqrt{3} \end{aligned} \right.$$

Substitute into 🦁 (oops, I mean equation $2.(c)$):[^1]
$$\begin{aligned} x_n&=\frac{(1+\sqrt{3})^{n-1}((3)-(1-\sqrt{3})(1))-(1-\sqrt{3})^{n-1}((3)-(1+\sqrt{3})(1))}{(1+\sqrt{3})-(1-\sqrt{3})} \\ \\ &=\frac{(1+\sqrt{3})^{n-1}(2+\sqrt{3})-(1-\sqrt{3})^{n-1}(2-\sqrt{3})}{(1+\sqrt{3})-(1-\sqrt{3})} \\ \\ &=\frac{\sqrt{3}+2}{2\sqrt{3}}(1+\sqrt{3})^{n-1}+\frac{\sqrt{3}-2}{2\sqrt{3}}(1-\sqrt{3})^{n-1} \end{aligned}$$

[^1]: Recently changed the Markdown compiler, LaTeX seems to have broken.

Now it's fixed.