Linear Recurrence Equation, ODE and Fields Extension

When we try to find the general formula of the Fibonacci Sequence or more general, $a_{n+2}=A{a}_{n+1}+B{a}_n$$a_{n+2}=Aa_{n+1}+Ba_n$.

Although the sequence is $\mathbb{N}$$\mathbb N$ valued function, some irrational number appears in the general formula.

For example, the general formula of the Fibonacci sequence is

$$\begin{array}{}\text{(1)}& a_n=\frac{1}{\sqrt{5}}({\left(\frac{1+\sqrt{5}}{2}\right)}^{n+1}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{n+1})\end{array}$$

Where does the irrational number come from?

Indeed, the irrational number comes from the algebraic field extension.

Consider the Fibonacci Sequence

$$\begin{array}{}\text{(2)}& a_{n+2}=a_{n+1}+a_n\end{array}$$

Represent the sequence to the formal power series $\begin{array}{c}f(X)=\sum _{n=0}^{\mathrm{\infty }}{a}_n\frac{X^n}{n!}\end{array}$$f(X)=\sum_{n=0}^{\infty}a_n\frac{X^n}{n!}\\$.

Then $\begin{array}{c}{f}^{\prime }(X)=\sum _{n=0}^{\mathrm{\infty }}{a}_{n+1}\frac{X^n}{n!},f^{″}(X)=\sum _{n=0}^{\mathrm{\infty }}{a}_{n+2}\frac{X^n}{n!}\end{array}$$f'(X)=\sum_{n=0}^{\infty}a_{n+1}\frac{X^n}{n!},f''(X)=\sum_{n=0}^{\infty}a_{n+2}\frac{X^n}{n!}\\$ .

Thus we can convert $a_{n+2}=a_{n+1}+a_n$$a_{n+2}=a_{n+1}+a_n$ to the ODE.

$$\begin{array}{}\text{(3)}& D^{2}f-Df-f=0\end{array}$$

View the solution space of $(D^2-D-1)f=0$$(D^2-D-1)f=0$ as an $\mathbb{Q}[D]$$\mathbb Q[D]$- Module. The annihilator of the space is $(D^2-D-1)$$(D^2-D-1)$.

It induces a natural quotient map and a field extension.

$$\begin{array}{}\text{(4)}& \mathbb{Q}\hookrightarrow \mathbb{Q}[D]\twoheadrightarrow \frac{\mathbb{Q}[D]}{(D^2-D-1)}\cong \mathbb{Q}\left(\frac{1+\sqrt{5}}{2}\right)\end{array}$$

$\mathrm{Gal}\left(\mathbb{Q}\left(\frac{1+\sqrt{5}}{2}\right)/\mathbb{Q}\right)\cong \{1,\sigma \}$$\mathrm{Gal}\left(\mathbb Q\left(\frac{1+\sqrt 5}{2}\right)/\mathbb Q\right)\cong\{1,\sigma\}$, where ${\sigma }^2=1$$\sigma^2=1$. By the ODE: An Algebraic Approach, solving the ODE is equivalence to solving the polynomials equation and $f(X)=C_1{e}^{\frac{1+\sqrt{5}}{2}X}+C_2{e}^{\frac{1-\sqrt{5}}{2}X}$$f(X)=C_1e^{\frac{1+\sqrt 5}{2} X}+C_2e^{ \frac{1-\sqrt 5}{2} X}$.

It looks like $f(X)$$f(X)$ is the linear combination of two elements in $\mathbb{Q}\left(\frac{1+\sqrt{5}}{2}\right)[[X]]$$\mathbb Q\left(\frac{1+\sqrt 5}{2}\right)[[X]]$. But $f\in \mathbb{Q}[[X]]⟺y=\sigma (y)$$f\in \mathbb Q[[X]]\iff y=\sigma (y)$.

Therefore, $\sigma (y)=\sigma (C_1)e^{\frac{1-\sqrt{5}}{2}X}+\sigma (C_2)e^{\frac{1+\sqrt{5}}{2}X}=y=C_1{e}^{\frac{1+\sqrt{5}}{2}X}+C_2{e}^{\frac{1-\sqrt{5}}{2}X}⟺C_1=\sigma (C_2),\sigma (C_1)=C_2$$\sigma(y)=\sigma(C_1) e^{\frac{1-\sqrt 5}{2}X}+\sigma(C_2)e^{\frac{1+\sqrt 5}{2}X}=y=C_1e^{\frac{1+\sqrt 5}{2} X}+C_2e^{ \frac{1-\sqrt 5}{2} X}\iff C_1=\sigma(C_2),\sigma(C_1)=C_2$.

Then $C_1+C_2=1=C_1+\sigma (C_1)$$C_1+C_2=1=C_1+\sigma(C_1)$ and $C_1\frac{1+\sqrt{5}}{2}+C_2\frac{1-\sqrt{5}}{2}=\frac{1}{2}+\frac{\sqrt{5}}{2}(C_1-C_2)=1$$C_1\frac{1+\sqrt 5}{2}+C_2\frac{1-\sqrt 5}{2}=\frac{1}{2}+\frac{\sqrt 5}{2}(C_1-C_2)=1$, so $C_1-\sigma (C_1)=\frac{1}{\sqrt{5}}$$C_1-\sigma(C_1)=\frac{1}{\sqrt 5}$.

Thus the rational part $\begin{array}{c}R(C_1)=\frac{1}{2}\end{array}$$R(C_1)=\frac{1}{2}\\$, irrational part $I(C_1)=\frac{1}{2\sqrt{5}}$$I(C_1)=\frac{1}{2\sqrt 5}$.

Hence $\begin{array}{c}{C}_1=\frac{1}{2}+\frac{1}{2\sqrt{5}}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right),C_2=\sigma (C_1)=-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)\end{array}$$C_1=\frac{1}{2}+\frac{1}{2\sqrt 5}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt 5}{2}\right),C_2=\sigma(C_1)=-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt 5}{2}\right)\\$.

Hence

$$\begin{array}{}\text{(5)}& a_n=\frac{1}{\sqrt{5}}({\left(\frac{1+\sqrt{5}}{2}\right)}^{n+1}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{n+1})\end{array}$$

It looks amazing, the field extension induced by ODE (see the ODE: An Algebraic Extension on my blog), and the Galois Group give the relationship of $C_1$$C_1$ and $C_2$$C_2$, help us find the value of $C_1,C_2.$$C_1,C_2.$