Finding the General Term of First and Second Order Linear Recurrences

I learned this here Recently, things have been quite competitive. Although I've done this set of problems before, I didn't study them carefully. Then, to avoid awkwardly explaining the problems, I dragged GJY into researching this until two or three in the morning. Actually, if I had learned about characteristic roots, this problem would be easy to see, but I hadn't. After asking many experts, I finally found the direction of characteristic roots. Because it was really late, I had to shamefully log off. The next morning, after spending a dozen minutes reading, it suddenly became clear, and I was amazed at how simple it was (not really). The calculation process is very simple, but the construction is still difficult. Fortunately, this is a general solution, so I can just use it a few times and memorize it. Characteristic roots seem to be from linear algebra (really seems like it).

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

1. First Order

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 solution 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 this is 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}$$

At this point, we can clearly see the form of $(a)$ in $(b')$. Furthermore, we establish connections between the variables.

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

At this point, we have obtained all the constants $p,x_0$ for the geometric sequence $b$, and we can find any term $x_n-x_0$, and naturally 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 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 solution 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')$ gives:

$$\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 this equation, they are "symmetric", considering the symmetry of the function graph.

We return 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 solving the characteristic equation $x^2-(2)x-(2)=0$ gives:

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

Substitute into 🦁 (no, it's 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 markdown compiler, LaTeX seems broken.

Now it's fixed.