A note on linear recursions

Abstract

We consider linear recursions of length two and related gap recursions where the indices may not be consecutive integers. Given a linear recursion of length two, we prove the existence of an explicit linear recursion of length $\mathcal{l}$ with arbitrary distance between indices. Conversely, it is shown under some mild assumption that a linear recursion of length $\mathcal{l}$ can be reduced to one of length two.

Keywords:

• Fibonacci Number
• Linear Recursion
• Recurrence relation

1. Introduction

The sequence of Fibonacci numbers F_n is defined by the recursion $F_{n+1}=F_n+F_{n-1}$ for integer $n\in \mathbb{N},$ starting with the initial values $F_0=0$ and $F_1=1.$ Livio (2002) provided an explicit formula for the nth Fibonacci number, i.e. (1) $$F_n=\frac{1}{\sqrt{5}}\left(G^n-{(-g)}^n\right)\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}(n\in {\mathbb{N}}_0),$$(1) where $G:=\frac{1}{2}(\sqrt{5}+1)$ is the golden ratio and $g:=G^{-1}=\frac{1}{2}(\sqrt{5}-1).$ It is an easy exercise to prove this formula by induction or using the associated generating function.

Fibonacci numbers appear in various ways in different areas. In botany, phyllotaxis is the study of the arrangement of leaves on a plant stem. In 1830, Schimper (1830) observed that the ratio of the number of circuits divided by the number of leaves—the so-called divergence—in the spiral configurations often result as quotients of Fibonacci numbers $F_k/F_{k+2}$ with gap; for example, the divergence is 1/3 for hazel, 2/5 for apricot, 3/8 for pear, and 5/13 for almond (cf (Hellwig & Neukirchner, 2010)). The sequence of rational numbers $F_k/F_{k+2}$ is called the Braun-Schimper sequence (named after Alexander Braun a colleague of Schimper). In 2015 Wang, Li, Kong, and He (2015) discovered that a fractal dimension of polar bear hairs is close to the golden ratio 1.618…. Sinha (2017) showed amazing applications of Fibonacci numbers in nature including constructing security coding. Blankenship (2021) linked the Fibonacci sequence to music and Guo (2021) used the Fibonacci sequence to make predictions on the Parkfield earthquake sequence. Recently, Postavaru and Toma (2022) studied the time scale Fibonacci sequences satisfying the Friedmann-Lemaître-Robertson-Walker (FLRW) dynamic equation on time scale, which is an exact solution of Einstein’s field equations of general relativity for expanding homogeneous and isotropic universe. They investigated the results based on the dynamic equations on time scale describes the Fibonacci numbers. In the same year, Basak (2022) proposed to construct a philosophical theory based on unexplained natural phenomena, observing the golden ratio and Fibonacci sequence in art and nature such as plants, animals, storm and universe. He also discussed these phenomena within his philosophical aspects based on the literature evidences.

Since Fibonacci sequence is in the form of a linear recursion of length two, it inspires us to consider any arbitrary recursions of length two and higher length. It may come as a surprise that any number of further recursions for Fibonacci numbers can be formed with arbitrary distances between the indices. For example, for every pair of positive integers k and $\mathcal{l},$ there exist coefficients $\gamma ,\delta$ depending only on $k,\mathcal{l}$ such that (2) $$F_{n+k}=\gamma F_n+\delta F_{n-\mathcal{l}}$$(2) for every $n\in \mathbb{N};$ we shall call this a gap recursion. In fact, the equations for $n=\mathcal{l}$ and $n=\mathcal{l}+1$ determine γ and δ and the verification of the gap recursion simply follows from the classical recursion formula by induction. This yields (3) $$F_{n+k}=\frac{F_{k+\mathcal{l}}}{F_{\mathcal{l}}}{F}_n+\left(F_{k+\mathcal{l}+1}-\frac{F_{k+\mathcal{l}}{F}_{\mathcal{l}+1}}{F_{\mathcal{l}}}\right)F_{n-\mathcal{l}}$$(3) or (4) $$F_{\mathcal{l}}{F}_{n+k}=F_{k+\mathcal{l}}{F}_n+(F_{k+\mathcal{l}+1}{F}_{\mathcal{l}}-F_{k+\mathcal{l}}{F}_{\mathcal{l}+1})F_{n-\mathcal{l}}$$(4) for arbitrary positive integers $k,\mathcal{l}.$

In this short note, we study the more general situation of a sequence of real numbers X_n satisfying a recursion of the form (5) $$X_n=\alpha X_{n-1}+\beta X_{n-2},$$(5) where α, β are again fixed real numbers. Our aims are to answer the following questions:

1. For every positive integers $k,\mathcal{l}$ and distinct $1\le m_1,\dots ,m_{\mathcal{l}}\le n,$ do there exist coefficients ${\gamma }_1,\dots ,{\gamma }_{\mathcal{l}}$ such that (6) $$X_{n+k}=\sum _{i=1}^{\mathcal{l}}{\gamma }_i{X}_{n-m_i}?$$(6) And, in case of their existence, is there a corresponding explicit formula for X_n in terms of the gap recursion?

2. Conversely, let $X_n={\sum }_{i=1}^{\mathcal{l}}{\gamma }_i{X}_{n-i}$ for $n\ge \mathcal{l}$ with a positive integer $\mathcal{l}\ge 2$ and real numbers γ_i. Are there two real numbers α, β such that (7) $$X_n=\alpha X_{n-1}+\beta X_{n-2}$$(7)

for every integer $n\ge 2$?

We give the answer to the first and the second question in Sections 2 and 3, respectively by applying fundamental techniques from linear algebra and elementary calculations with complex numbers.

2. Extension of the recursion of length two

Given any sequence of real numbers X_n satisfying the following recursion (8) $$X_n=\alpha X_{n-1}+\beta X_{n-2}\hspace{1em}\text{for}\mathrm{ }n\ge 2,$$(8) it follows that, for any positive integer $\mathcal{l},$ we have (9) $$X_{n+\mathcal{l}}=A_{\mathcal{l}}{X}_n+B_{\mathcal{l}}{X}_{n-1}\hspace{1em}\text{for}\mathrm{ }n\ge 1,$$(9) where $A_n:=\alpha A_{n-1}+\beta A_{n-2}$ with $A_0=1,A_1=\alpha ,$ and $B_n:=\alpha B_{n-1}+\beta B_{n-2}$ with $B_0=0,B_1=\beta .$ Hence, for any positive integers $k,\mathcal{l}$ and non-negative integers $m_1,m_2,\dots ,m_{\mathcal{l}}$ where $m_{\mathcal{l}}\ge m_j$ for all j, $B_{m_{\mathcal{l}}-m_i}\ne 0$ for $i=1,\dots ,{\mathcal{l}}^{*}$ and $B_{m_{\mathcal{l}}-m_i}=0$ for $i={\mathcal{l}}^{*}+1,\dots ,\mathcal{l}-1,$ we obtain (10) $$X_{n+k}=A_{m_{\mathcal{l}}+k}{X}_{n-m_{\mathcal{l}}}+B_{m_{\mathcal{l}}+k}{X}_{n-m_{\mathcal{l}}-1},$$(10) (11) $$X_{n-m_j}=A_{m_{\mathcal{l}}-m_j}{X}_{n-m_{\mathcal{l}}}+B_{m_{\mathcal{l}}-m_j}{X}_{n-m_{\mathcal{l}}-1}\hspace{1em}\text{for}\mathrm{ }1\le j<\mathcal{l}.$$(11)

If ${\mathcal{l}}^{*}=0,$ it is easy to see that (12) $$X_{n+k}=-\sum _{i=1}^{\mathcal{l}-1}{X}_{n-m_i}+\left(A_{m_{\mathcal{l}}+k}+\sum _{i=1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\right)X_{n-m_{\mathcal{l}}}+B_{m_{\mathcal{l}}+k}{X}_{n-m_{\mathcal{l}}-1}.$$(12)

If $B_{m_{\mathcal{l}}+k}\ne 0$ and ${\mathcal{l}}^{*}\ne 0,$ we derive (13) $$\begin{array}{c}{X}_{n-m_{\mathcal{l}}-1}=\sum _{i=1}^{{\mathcal{l}}^{*}}\frac{1}{{\mathcal{l}}^{*}{B}_{m_{\mathcal{l}}-m_i}}{X}_{n-m_i}+\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{X}_{n-m_i}+\\ -\left(\sum _{i=1}^{{\mathcal{l}}^{*}}\frac{A_{m_{\mathcal{l}}-m_i}}{{\mathcal{l}}^{*}{B}_{m_{\mathcal{l}}-m_i}}-\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\right)X_{n-m_{\mathcal{l}}}.\end{array}$$(13)

This implies (14) $$X_{n+k}=B_{m_{\mathcal{l}}+k}\left(\sum _{i=1}^{\mathcal{l}}{\mathcal{P}}_i{X}_{n-m_i}\right),$$(14) where (15) $${\mathcal{P}}_i=\{\begin{array}{cc}\frac{1}{{\mathcal{l}}^{*}{B}_{m_{\mathcal{l}}-m_i}}\hfill & \mathit{\text{if}}\mathrm{ }1\le i\le {\mathcal{l}}^{*},\hfill \\ 1\hfill & \mathit{\text{if}}\mathrm{ }{\mathcal{l}}^{*}+1\le i<\mathcal{l},\hfill \\ \frac{A_{m_{\mathcal{l}}+k}}{B_{m_{\mathcal{l}}+k}}-\sum _{i=1}^{{\mathcal{l}}^{*}}\frac{A_{m_{\mathcal{l}}-m_i}}{{\mathcal{l}}^{*}{B}_{m_{\mathcal{l}}-m_i}}+\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\hfill & \mathit{\text{if}}\mathrm{ }i=\mathcal{l},\hfill \end{array}$$(15)

If $B_{m_{\mathcal{l}}+k}=0$ and ${\mathcal{l}}^{*}\ne 0,$ we obtain similarly (16) $$\begin{array}{c}{X}_{n-m_{\mathcal{l}}-1}=\sum _{i=2}^{{\mathcal{l}}^{*}}\frac{1}{({\mathcal{l}}^{*}-1)B_{m_{\mathcal{l}}-m_i}}{X}_{n-m_i}+\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{X}_{n-m_i}+\\ -\left(\sum _{i=2}^{{\mathcal{l}}^{*}}\frac{A_{m_{\mathcal{l}}-m_i}}{({\mathcal{l}}^{*}-1)B_{m_{\mathcal{l}}-m_i}}-\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\right)X_{n-m_{\mathcal{l}}}.\end{array}$$(16)

This implies (17) $$X_{n+k}=\sum _{i=1}^{\mathcal{l}}{\mathcal{Q}}_i{X}_{n-m_i},$$(17) where (18) $${\mathcal{Q}}_i=\{\begin{array}{cc}-1\hfill & \mathit{\text{if}}\mathrm{ }i=1,\hfill \\ \frac{B_{m_{\mathcal{l}}-m_1}}{({\mathcal{l}}^{*}-1)B_{m_{\mathcal{l}}-m_i}}\hfill & \mathit{\text{if}}\mathrm{ }2\le i\le {\mathcal{l}}^{*},\hfill \\ B_{m_{\mathcal{l}}-m_1}\hfill & \mathit{\text{if}}\mathrm{ }{\mathcal{l}}^{*}+1\le i<\mathcal{l},\hfill \\ A_{m_{\mathcal{l}}+k}+A_{m_{\mathcal{l}}-m_1}-\sum _{i=2}^{{\mathcal{l}}^{*}}\frac{A_{m_{\mathcal{l}}-m_i}}{({\mathcal{l}}^{*}-1)B_{m_{\mathcal{l}}-m_i}}+\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\hfill & \mathit{\text{if}}\mathrm{ }i=\mathcal{l}\hfill \end{array}.$$(18)

This leads to

Theorem 1.

Given real numbers α, β, let $X_n=\alpha X_{n-1}+\beta X_{n-2}$. Define

$A_n:=\alpha A_{n-1}+\beta A_{n-2}$ with $A_0=1,A_1=\alpha ,$ and

$B_n:=\alpha B_{n-1}+\beta B_{n-2}$ with $B_0=0,B_1=\beta .$

Then, for every pair of positive integers $k,\mathcal{l}$ and non-negative integers $m_1,m_2,\dots ,m_{\mathcal{l}}$, where $m_{\mathcal{l}}\ge m_j$ for all $j\le \mathcal{l}$, let ${\mathcal{l}}^{*}\le \mathcal{l}-1$ such that $B_{m_{\mathcal{l}}-m_i}\ne 0$ for $i=1,\dots ,{\mathcal{l}}^{*}$ and $B_{m_{\mathcal{l}}-m_i}=0$ for $i={\mathcal{l}}^{*}+1,\dots ,\mathcal{l}-1$. Then (19) $$X_{n+k}=\{\begin{array}{cc}{B}_{m_{\mathcal{l}}+k}\left(\sum _{i=1}^{\mathcal{l}}{\mathcal{P}}_i{X}_{n-m_i}\right)\hfill & if\mathrm{ }{B}_{m_{\mathcal{l}}+k}\ne 0,{\mathcal{l}}^{*}\ne 0,\hfill \\ \sum _{i=1}^{\mathcal{l}}{\mathcal{Q}}_i{X}_{n-m_i}\hfill & if\mathrm{ }{B}_{m_{\mathcal{l}}+k}=0,{\mathcal{l}}^{*}\ne 0,\hfill \\ B_{m_{\mathcal{l}}+k}{X}_{n-m_{\mathcal{l}}-1}+\sum _{i=1}^{\mathcal{l}}{\mathcal{R}}_i{X}_{n-m_i}\hfill & if\mathrm{ }{\mathcal{l}}^{*}=0,\hfill \end{array}$$(19)

where (20) $${\mathcal{P}}_i=\{\begin{array}{cc}\frac{1}{{\mathcal{l}}^{*}{B}_{m_{\mathcal{l}}-m_i}}\hfill & \mathit{\text{if}}\mathrm{ }1\le i\le {\mathcal{l}}^{*},\hfill \\ 1\hfill & \mathit{\text{if}}\mathrm{ }{\mathcal{l}}^{*}+1\le i<\mathcal{l},\hfill \\ \frac{A_{m_{\mathcal{l}}+k}}{B_{m_{\mathcal{l}}+k}}-\sum _{i=1}^{{\mathcal{l}}^{*}}\frac{A_{m_{\mathcal{l}}-m_i}}{{\mathcal{l}}^{*}{B}_{m_{\mathcal{l}}-m_i}}+\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\hfill & \mathit{\text{if}}\mathrm{ }i=\mathcal{l},\hfill \end{array}$$(20) (21) $${\mathcal{Q}}_i=\{\begin{array}{cc}-1\hfill & \mathit{\text{if}}\mathrm{ }i=1,\hfill \\ \frac{B_{m_{\mathcal{l}}-m_1}}{({\mathcal{l}}^{*}-1)B_{m_{\mathcal{l}}-m_i}}\hfill & \mathit{\text{if}}\mathrm{ }2\le i\le {\mathcal{l}}^{*},\hfill \\ B_{m_{\mathcal{l}}-m_1}\hfill & \mathit{\text{if}}\mathrm{ }{\mathcal{l}}^{*}+1\le i<\mathcal{l},\hfill \\ A_{m_{\mathcal{l}}+k}+A_{m_{\mathcal{l}}-m_1}-\sum _{i=2}^{{\mathcal{l}}^{*}}\frac{A_{m_{\mathcal{l}}-m_i}}{({\mathcal{l}}^{*}-1)B_{m_{\mathcal{l}}-m_i}}+\sum _{i={\mathcal{l}}^{*}+1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\hfill & \mathit{\text{if}}\mathrm{ }i=\mathcal{l},\hfill \end{array}$$(21)

and (22) $${\mathcal{R}}_i=\{\begin{array}{cc}-1\hfill & \mathit{\text{if}}\mathrm{ }1\le i<\mathcal{l},\hfill \\ A_{m_{\mathcal{l}}+k}+\sum _{i=1}^{\mathcal{l}-1}{A}_{m_{\mathcal{l}}-m_i}\hfill & \mathit{\text{if}}\mathrm{ }i=\mathcal{l}.\hfill \end{array}$$(22)

3. Reduction of the recursion of length $\mathcal{l}$

We consider the recursion (23) $$X_n=\sum _{i=1}^{\mathcal{l}}{\gamma }_i{X}_{n-i},$$(23) where $\mathcal{l}\ge 2$ is a positive integer and the γ_i’s are real numbers such that ${\sum }_{i=1}^{\mathcal{l}}{\gamma }_i^2\ne 0.$ Recalling the question from the introduction, is there a relation $X_n=\alpha X_{n-1}+\beta X_{n-2}$ for some real numbers α, β?

In 2017, Wiboonton (2017) collected several methods for research on the Fibonacci sequence. One of them relies on matrix calculus. We shall follow this approach and consider: (24) $$\left[\begin{array}{c}{X}_{n+1}\\ X_n\end{array}\right]=\left[\begin{array}{cc}\alpha & \beta \\ 1& 0\end{array}\right]\left[\begin{array}{c}{X}_n\\ X_{n-1}\end{array}\right].$$(24)

This implies, for any positive integer k, (25) $$\left[\begin{array}{c}{X}_{n+k}\\ X_{n+k-1}\end{array}\right]={\left[\begin{array}{cc}\alpha & \beta \\ 1& 0\end{array}\right]}^k\left[\begin{array}{c}{X}_n\\ X_{n-1}\end{array}\right].$$(25)

In the sequel we assume that α and β satisfy ${\alpha }^2+4\beta \ne 0$ (in order to have a non-vanishing discriminant). We can diagonalize $\left[\begin{array}{cc}\alpha & \beta \\ 1& 0\end{array}\right]$ by an invertible matrix $\mathcal{P}:=\left[\begin{array}{cc}{\lambda }_{-}& {\lambda }_{+}\\ 1& 1\end{array}\right]$ and a diagonal matrix $\mathcal{D}:=\left[\begin{array}{cc}{\lambda }_{-}& 0\\ 0& {\lambda }_{+}\end{array}\right]$ such that (26) $$\left[\begin{array}{cc}\alpha & \beta \\ 1& 0\end{array}\right]=\mathcal{P}\mathcal{D}{\mathcal{P}}^{-1},$$(26) where ${\lambda }_{-}:=\frac{\alpha -\sqrt{{\alpha }^2+4\beta }}{2}$ and ${\lambda }_{+}:=\frac{\alpha +\sqrt{{\alpha }^2+4\beta }}{2}.$

If we set ${\mathcal{X}}_n=\left[\begin{array}{c}{X}_{n+1}\\ X_n\end{array}\right],$ then we can rewrite relation (23)(23) $$X_n=\sum _{i=1}^{\mathcal{l}}{\gamma }_i{X}_{n-i},$$(23) as (27) $${\mathcal{X}}_n=\sum _{i=1}^{\mathcal{l}}{\gamma }_i{\mathcal{X}}_{n-i}.$$(27)

Applying the above matrices, we obtain (28) $$\mathcal{P}{\mathcal{D}}^{\mathcal{l}}{\mathcal{P}}^{-1}{\mathcal{X}}_{n-\mathcal{l}}=\sum _{i=1}^{\mathcal{l}}{\gamma }_i\mathcal{P}{\mathcal{D}}^{\mathcal{l}-i}{\mathcal{P}}^{-1}{\mathcal{X}}_{n-\mathcal{l}},$$(28) or (29) $$\mathcal{P}\left({\mathcal{D}}^{\mathcal{l}}-\sum _{i=1}^{\mathcal{l}}{\gamma }_i{\mathcal{D}}^{\mathcal{l}-i}\right){\mathcal{P}}^{-1}{\mathcal{X}}_{n-\mathcal{l}}=0.$$(29)

Now, we set $\mathcal{P}({\mathcal{D}}^{\mathcal{l}}-{\sum }_{i=1}^{\mathcal{l}}{\gamma }_i{\mathcal{D}}^{\mathcal{l}-i}){\mathcal{P}}^{-1}=0.$ This implies ${\mathcal{D}}^{\mathcal{l}}={\sum }_{i=1}^{\mathcal{l}}{\gamma }_i{\mathcal{D}}^{\mathcal{l}-i}.$ Hence, we have (30) $$\left[\begin{array}{cc}{\lambda }_{-}^{\mathcal{l}}& 0\\ 0& {\lambda }_{+}^{\mathcal{l}}\end{array}\right]=\left[\begin{array}{cc}\sum _{i=1}^{\mathcal{l}}{\gamma }_i{\lambda }_{-}^{\mathcal{l}-i}& 0\\ 0& \sum _{i=1}^{\mathcal{l}}{\gamma }_i{\lambda }_{+}^{\mathcal{l}-i}\end{array}\right].$$(30)

Then, (31) $${\lambda }_{-}^{\mathcal{l}}=\sum _{i=1}^{\mathcal{l}}{\gamma }_i{\lambda }_{-}^{\mathcal{l}-i}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{and}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{\lambda }_{+}^{\mathcal{l}}=\sum _{i=1}^{\mathcal{l}}{\gamma }_i{\lambda }_{+}^{\mathcal{l}-i}.$$(31)

To solve this system, we assume that there are two complex numbers z₁ and z₂ satisfying $x^{\mathcal{l}}={\sum }_{i=1}^{\mathcal{l}}{\gamma }_i{x}^{\mathcal{l}-i}.$ If we set $z_1:={\lambda }_{-}=\frac{\alpha -\sqrt{{\alpha }^2+4\beta }}{2}$ and $z_2:={\lambda }_{+}=\frac{\alpha +\sqrt{{\alpha }^2+4\beta }}{2},$ then we get $\alpha =z_1+z_2$ and $\beta =-z_1{z}_2.$ In case that z₁ and z₂ are real numbers, both α and β are also real, however, it remains to verify whether ${\alpha }^2+4\beta$ is non-vanishing or not.

For otherwise, we choose $z_1=z\in \mathbb{C}\setminus \mathbb{R}$ which is a root of $x^{\mathcal{l}}={\sum }_{i=1}^{\mathcal{l}}{\gamma }_i{x}^{\mathcal{l}-i}$ and its conjugate $z_2=\overline{z}$ is also a root. In this case the values α and β are $2\mathfrak{R}(z)$ and $-{\left|z\right|}^2,$ respectively. Furthermore, ${\alpha }^2+4\beta \ne 0$ since z is not a real number.

Summing up, we arrive

Theorem 2.

Let $\mathcal{l}\ge 2$ be a positive integer and $X_n={\sum }_{i=1}^{\mathcal{l}}{\gamma }_i{X}_{n-i}$ be a linear homogeneous recursion with initial conditions X_i for $i=0,1,\dots ,\mathcal{l}-1$ and suppose that the sequence of X_n satisfies at least one of the following statements:

1. the corresponding characteristic equation has two real roots r₁ and r₂ such that $r_1^2+4r_2\ne 0$ and the quadratic recursion (32) $$Y_n=(r_1+r_2)Y_{n-1}-r_1{r}_2{Y}_{n-2}$$(32) with the initial conditions of Y ₀ = X₀ and Y ₁ = X₁ leads to Y _i = X_i for all $i=2,3\dots ,\mathcal{l}-1,$

2. its characteristic equation has a complex root z such that z is not a real number and the quadratic recursion (33) $$Y_n=2\mathfrak{R}(z)Y_{n-1}-|z{|}^2{Y}_{n-2}$$(33)

   with the initial conditions of Y ₀ = X₀ and Y ₁ = X₁ leads to Y _i = X_i for all $i=2,3\dots ,\mathcal{l}-1.$

Then, Y _n = X_n for all n.

Applying this to the second question from the beginning, it follows that there always exist two real numbers α, β satisfying $X_n=\alpha X_{n-1}+\beta X_{n-2}$ whenever the associated characteristic equation satisfies at least one of the two conditions in Theorem 2.

4. Applications and examples

To illustrate the theorems from above, we shall consider the well-known recursion for Fibonacci number F_n.

Example 3.

It is easy to see that if the indices are restricted to the set of non-negative odd or even integer, there are also recursions, namely (34) $$F_{n+2}=3F_n-F_{n-2}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\left(n\ge 2\right).$$(34)

Indeed, we may apply Theorem 1 with $A_n=F_{n+1}$ and B_n = F_n for any positive integer n. We deduce (35) $$F_{n+k}=F_{k+\mathcal{l}}\left(\frac{1}{F_{\mathcal{l}}}{F}_n+\left(\frac{F_{k+\mathcal{l}+1}}{F_{k+\mathcal{l}}}-\frac{F_{\mathcal{l}+1}}{F_{\mathcal{l}}}\right)F_{n-\mathcal{l}}\right)$$(35) or (36) $$F_{\mathcal{l}}{F}_{n+k}=F_{k+\mathcal{l}}{F}_n+\left(F_{k+\mathcal{l}+1}{F}_{\mathcal{l}}-F_{k+\mathcal{l}}{F}_{\mathcal{l}+1}\right)F_{n-\mathcal{l}}$$(36) for any positive integers $k,\mathcal{l}$ (that are formulae (Guo, 2021) and (Hellwig & Neukirchner, 2010) from the introduction). For the special case $k=2,\mathcal{l}=2$, we get (37) $$F_2{F}_{n+2}=F_4{F}_n+\left(F_5{F}_2-F_4{F}_3\right)F_{n-2}$$(37) or (38) $$F_{n+2}=3F_n-F_{n-2}$$(38)

(which is formula (34)(34) $$F_{n+2}=3F_n-F_{n-2}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\left(n\ge 2\right).$$(34) above).

On the other hand, by Theorem 2, the corresponding characteristic equation of the recursion $F_n=3F_{n-2}-F_{n-4}$ is $x^4-3x^2+1$ which has four distinct real roots, namely (39) $$\frac{1}{2}\left(-1-\sqrt{5}\right),\hspace{1em}\frac{1}{2}\left(1-\sqrt{5}\right),\hspace{1em}\frac{1}{2}\left(-1+\sqrt{5}\right),\hspace{1em}\frac{1}{2}\left(1+\sqrt{5}\right).$$(39)

• If the initial values are $F_0=0,F_1=1,F_2=1,F_3=2$, we get that $Y_n=Y_{n-1}+Y_{n-2}.$

• If the initial conditions are $F_0=0,F_1=1,F_2=-1,F_3=2$, we get that $Y_n=-Y_{n-1}+Y_{n-2}.$

5. Conclusions

From Sections 2 and 3, we conclude the main results as follows:

Remark 4

In Theorem 1 (Section 2), we extend the length of a linear recursion of length two to one of length $\mathcal{l}$. Conversely, we can reduce the length of a linear recursion of length $\mathcal{l}$ to one of length two in Theorem 2 (Section 3).

Remark 5

We observe that a linear recursion of length $\mathcal{l}$ that is constructed from Theorem 1 (Section 2) can always be reduced to linear recursion of length two by using the method in Theorem 2 (Section 3). However, for any linear recursion of length $\mathcal{l}$, if it is written in any form of linear recursions of length two obtained by Theorem 2 but there is no initial condition of each recursion of length two which corresponds to one of length $\mathcal{l}$, we cannot conclude that there is not a linear recursion of length two which represents the same sequence.

Acknowledgments

The authors are grateful to the anonymous referee for her or his valuable comments and corrections. The authors would like to thank National Research Council of Thailand (NRCT) and Walailak University for facilities and financial supports.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Research Council of Thailand (NRCT) and Walailak University under Grant number NRCT5-RSA63019-06 (2563NRCT322800).