Some remarks on recursive sequence of fibonacci type

1.   Introduction and main results

A recursive or recurrence sequence is usually defined by a recurrence procedure; that is, any term is the sum of preceding terms. One of the most famous recurrence sequence is the Fibonacci sequence $(F_n)_n$, denominated in honor of Leonardo Fibonacci. This sequence of integers constitutes a numerical progression with historical roots tracing back to the 13th century and defined as $F_0 = F_1 = 1$ and $F_{n+2} = F_{n+1}+F_n$ for all $n\ge 0$. Its significance transcends mere numerical abstraction, finding pervasive manifestation throughout natural phenomena. Scholarly inquiries spanning epochs have substantiated its remarkable attributes and multifaceted intersections with disparate domains of academic pursuit, notably encompassing Algebra, Geometry, and Number Theory, among others. In particular, when focusing on the combinatorial properties of words, one can identify Fibonacci strings as the words corresponding to the Fibonacci numbers obtained by fixing the first two initial letters ^[1]. Also, this concept may be applied to study some properties related the behavior of molecules in DNA ^[2].

Many authors have studied some generalization of the Fibonacci sequence through either preserving the original recurrence relation while modifying the initial terms or by maintaining the initial terms while introducing slight modifications to the recursive relation. In ^[3,4,5], the authors studied the $k$-Jacobsthal-Lucas and (s, t)-Jacobthal-Lucas sequences. In the first part of this paper, we focus on the generalized $k$-Fibonacci-like sequence denoted as $(G_{k, n})_{n \geq 0}$, or simply $(G_n)_n$ in contexts where ambiguity is absent, where $k$ represents a positive integer. This sequence, comprised of integer values, originates from initial terms $a$ and $b$, and is defined as

where $a, b\in {\mathbb N}$, the set of non-negative integers. In particular, we have

(1) if $a = 0, b = 1$, then $\{G_{k, n} \}$ is the $k$-Fibonacci sequence $\{F_{k, n} \}$ ^[6];

(2) if $a = 2$, $b = 2$, then $\{G_{k, n} \}$ is the $k$-Fibonacci like sequence $\{S_{k, n} \}$ ^[7];

(3) if $k = 1, a = 0, b = 1$, then $\{G_{k, n} \}$ is the classical Fibonacci sequence $\{F_{n} \}$;

(4) if $k = 1, a = 1, b = 3$, then $\{G_{k, n} \}$ is the classical Lucas sequence $\{L_{n} \}$;

(5) if $k = 1, a = 2, b = 2$, then $\{G_{k, n} \}$ is the Fibonacci-like sequence $\{S_{n} \}$ ^[8];

(6) if $k = 2, a = 2, b = 1$, then $\{G_{k, n} \}$ is the sequence $\{H_{n} \}$ defined in ^[9].

The enduring intrigue surrounding the Fibonacci sequence $(F_n)$ has engendered sustained scholarly exploration into its intrinsic properties and practical applications. Noteworthy among these investigations is the work by Mak ^[10], which elucidated the exponential growth of the Fibonacci sequence $(F_n)_{n\geq0}$ with respect to the index $n$, characterized by a growth rate defined by the golden ratio $\varphi = (1 + \sqrt{5})/2 = 1.61803398\ldots$. A similar result is obtained when studying $k$-Fibonacci-like sequence. Indeed, a pivotal property of the $k$-Fibonacci-like sequence is encapsulated by Binet's formula, as expounded in [11, Theorem 2.4]

where $\sigma_k = \frac{k+\sqrt{k^2+4} }{2}$ is known as the $k$-metallic ratio and $\varphi_k = \frac{k- \sqrt{k^2+4} }{2}$. That is, $\sigma_k$ and $\varphi_k$ are roots of the characteristic equation $x^2 = kx + 1$ associated with the recurrence relation (1.1). In particular if $a = 0$ and $b = 1$ then

and if $a = 1$ and $b = k$ then

for all $n\ge 0$. We refer to ^{[6,7,11,12,13,14]} for more details about this sequence.

Let $(\omega_i)_{i\geq1}$ be a sequence of independent, identically distributed random variables defined on the probability space $(\Omega, \mathcal T, {\mathbb P})$ such that

For an elementary event $w\in\mathcal{T}$, we define the random walk whose increments are given by $(G_{k, n})_{n\geq1}$, i.e.,

In Section 2, we investigate the $k$-Fibonacci random walk and determine the probability of its return to the origin. More precisely, let

where $"\sharp C"$ denotes the cardinality of a given set $C$. We establish first a necessary and sufficient condition so that $\hat G_n$ reaches $0$ at least once (Proposition 2.1). Furthermore, we are interested in the set ${\mathsf N}$ of walks returning infinitely many times to zero; that is, ${\mathsf N} = \Big\{ w\in\mathcal{T} \; |\; \sharp G(w) = \infty\Big\}.$ We will describe geometrically the size of this set by computing its Hausdorff and Packing dimensions denoted by $\dim_H({\mathsf N}) = \dim_P({\mathsf N})$, respectively (for further elaboration on this concept of dimension, we direct the reader to ^[15,16]). Our first main result is the following.

Theorem 1.1. Assume that $a = 0$ and $b\neq 0$; then, for $i\in \mathbb{N},$ we have

Moreover, $\dim_H({\mathsf N}) = \dim_P({\mathsf N}) = \frac1{3}.$

Remark 1.1. (1) For $k = 1$, the result may be found in ^[17,18].

(2) Clearly ${\mathbb P}({\mathsf N}) = 0$, for this we will study the Haudsorff and packing dimension of ${\mathsf N}$.

One of the most general generalizations of the Fibonacci sequence is the Tribonacci sequence, originally studied by Feinberg in 1963 ^[19]. Since then, many generalizations have been studied, with many interesting properties including Binet formulas, generating functions and summation formulas ^{[20,21,22,23,24,25]}. This sequence is defined as

When ${\mathsf T}_0 = 0$, ${\mathsf T}_1 = {\mathsf T}_2 = 1$, then ${\mathsf T}_n$ is the standard Tribonacci sequence, whereas ${\mathsf T}_0 = 3$, ${\mathsf T}_1 = 1$ and ${\mathsf T}_2 = 3$ gives the Tribonacci-Lucas sequence ^[26]. In ^[27], the value of the Fibonacci sequence on the diagonal sums of Pascal's triangle was provided and the analog result for Tribonacci sequence with the initial numbers ${\mathsf T}_0 = {\mathsf T}_1 = 1$ and ${\mathsf T}_2 = 2$ was proven. This explains why this special sequence, with the given initial numbers, obtains the status of "basic" series. Thus, the initial numbers of the Tribonacc-type series are crucial for establishing some properties of this sequence, such as the calculation of the general terms using Binet formulas.

By recalling the formula (1.2), one can study the asymptotic behavior of the sequence $(\xi_{k, n})_n$ by

(see Figure 1 for different value of $k, a$ and $b$). It is well know that [11, Corollary 2.13] we have $\lim\limits_{n\to \infty} \xi_{k, n} = \sigma_k: = \frac{k+\sqrt{k^2+4}}{2}.$

In this paper, we will study the asymptotic behavior of the sequence $\Big(\frac{ {\mathsf T}_{n+1}}{ {\mathsf T}_{n}}\Big)$. In ^[26], the author gives a complete discussion, on Binet formula, with arbitrary initial numbers. They proved that

where $({\mathsf T}_0, {\mathsf T}_1, {\mathsf T}_2) = (a, b, c)$, $\phi = 1.839286$ is the real solution of the equation $x^3-x^2-x-1 = 0$, $\gamma\pi = \arccos \Big(\frac{(1-\phi)\sqrt{\phi}}{2} \Big) = 124.688997\ldots^{\circ}$, $\theta = 5.470354\ldots$, $\alpha = 3.857689\ldots$ and $\omega_3$ is the phase shift introduced in order to verify the initial conditions. In Section 3, we will investigate the Tribonacci sequence with $a = b = c = 1$. We will first study the limiting behavior of the sequence $({\mathsf T}_n)_{n\ge 0}$ through the limiting distribution of a Markov chain that encodes the entire sequence. More precisely, we will prove the following result.

Theorem 1.2. Let $({\mathsf T}_n)$ be the Tribonacci sequence with initial terms ${\mathsf T}_0 = {\mathsf T}_1 = {\mathsf T}_2 = 1$. Then

where ${\mathsf p}$ is the unique solution of $x+\sqrt{x}(x+1)+1 = 0$ on $(0, 1).$ In particular,

2.   Return of $k$-Fibonacci-like random walks

In this section, we study the probability of return of the $k$-Fibonacci random walk to the origin. For $a = 0$ and $b\neq 0$, we give a necessary and sufficient condition to obtain $\sum_{i = 1}^nw_i G_i = 0$. For this, we consider, the finite sequences,

We will assume throughout this section that, if $a = 0$, then $(k, b)\notin (1, 1)$; otherwise, we get the trivial case $G_i = 1$ for all $i\ge 1$.

Proposition 2.1. Consider the $k$-Fibonacci-like sequence $(G_i)_{i\geq0}$ defined in (1.1) and assume that $a = 0$ and $b\neq 0$. Let $w = (w_i)_{i\geq0}\in\mathcal{T}$, then $\hat G_n(w) = 0$ if and only if $n = 3 m$, for some integer $m > 0,$ and

The "if" portion of the theorem is self-evident, thus we will solely demonstrate the "only if" part. To facilitate this, we require the subsequent lemma.

Lemma 2.1. (1) For any $n\ge 1$, we have

(a) $\Big| \sum_{j = 0}^{n} \omega_j G_{j} \Big|\le G_{n} + \frac{1}{k}(G_{n+1} - b)$ if $n$ is even.

(b) $\Big| \sum_{j = 0}^{n} \omega_j G_{j} \Big|\le G_{n+1} + \frac{1}{k}(G_{n} - b)$ if $n$ is odd.

(2) Let $p\in {\mathbb N}$ and assume that $(\omega_p, \omega_{p+1}, \omega_{p+2}) \notin \{v_+, v_- \}$. Then

(a) $\Big| \sum_{j = p}^{p+2}\omega_j G_j\Big|\geq 2 G_{p}.$

(b) $|\hat G_{p+2}(w)| > 1.$

Proof. (1) By definition, we have

It follows that

Similarly, we obtain that

(a) Assume that $n = 2 n_1$. In this case, we have

(b) Assume that $n = 2n_1+1$. In this case, we have

as required.

(2) (a) Using (1.1), we have

We suppose that $\omega_{p+2} = 1$ (the case $w_{p+2} = -1$ is analogous). Considering all possible values of $(\omega_{p}, \omega_{p+1}, \omega_{p+2})$, the Eq (2.1) leads to

(b) If $p = 1$, then by using Lemma 2.1 (2), we obtain $|\hat G_{3}(w)| \geq 2G_1 > 1.$ Otherwise,

Now, using Lemma 2.1 (1) leads to

ⅰ. If $p-1$ is even, then $p\ge 3$. It follows that $G_{p} > b$ and then

ⅱ. If $p-1$ is odd, then $p\ge 2$. It follows that $G_{p-1} \ge b$ and then

□

Returning to the proof of Proposition 2.1, we assume that the condition $\hat G_n(w) = 0$ holds. Initially, it is noted that, since $b \neq 0$, then $n \geq 3$ due to $w_1 G_1 + w_2 G_2 \neq 0$. Consequently, by utilizing Lemma 2.1(2) (b), the result ensues through induction.

2.1.   Proof of Theorem 1.1

For $i \geq 1$, the initial statement of this theorem implies that $\hat G_n$ returns the origin precisely $i$ times if and only if $n \geq 3i$, where $\hat G_{3i} = 0$ and $\hat G_{3(i+1)} \neq 0$. It follows that

We consider the space of infinite sequences $\mathcal{A} = \big\{1, -1\big\}^\mathbb{N}$. Let $r$ and $p$ be positive integers such that $1\le p\le 2^r$. We consider the finite sequences

where $v_{i, j}\in \{1, -1\big\}$, for all $1\le i\le p$ and $1\le j\le r$, and $v^r_{i}\neq v^r_{t}$ for all $i\neq t$.

Lemma 2.2. Let $C = \{v^r_{1}, v^r_{2}, \ldots, v^r_{p}\}^ {\mathbb N}$. Then

Proof. We consider the metric $d$, defined for any couple $\Big((u_i)_i, (v_i)_i\Big)$ of $\mathcal{A}\times \mathcal{A}$, by

Endowed with this metric, $\big(\mathcal{A}, d\big)$ becomes a compact metric space. Now, we consider for all $i = 1, \ldots, p$ the mappings $T_i$ defined for any $w = (w_i)_i\in \mathcal{A}$, by

For $i\in\{1, 2, \ldots, p\}$ and for any $(u, v) = \Big((u_j)_j, (v_j)_j\Big)\in \mathcal{A}\times \mathcal{A}$, we have

This means that $T_i$ is a contracting similarity in the metric space $(\mathcal{A}, d)$, with contraction rates

Coming back to ^[28], one deduces the existence of a unique compact self-similar subset $F$ of $\mathcal{A}$, such that

Furthermore, we have $T_i(C) \cap T_t(C) = \emptyset,$ for any $i\neq t$. Hence, $C$ is a self-similar set satisfying the open set condition in the compact metric space $(\mathcal{A}, d)$ (see, for instance, ^[16,28,29]). Then, one can deduce the fractal dimension in [15,Theorem 9.3] and

□

Consider the event ${\bf w} = 1, k, 1, k, \ldots$ and define

Then

As a direct consequence of Proposition 2.1, we obtain that ${\mathsf N} = \{v_{+}, v_{-} \}^{\mathbb N}$ and then we may apply Lemma 2.2 when $p = 2$ and $r = 3$, which complete the proof of Theorem 1.1.

3.   A probabilistic approach to the Tribonacci sequence

A chain graph consists of the nodes $\{1, 2, \ldots, n \}$; such that the only edges are of the form $\{i, i+1\}$. We define the set $K$ in the graph such that we can not find $i\in \{1, 2, \ldots, n-1\}$ with both $(b_i, b_{i+1})\in \{(1, 1), (2, 2), (1, 2), (2, 0)\}$. Let $\Omega_n$ be the set of all $0, 1, 2$ vectors of length $n+1$ such that $b_1 = b_2 = b_3 = 0$ and let $\{4, \ldots, n\}$ in $K$. Denote by $\# \Omega_n$ the number of elements in the set. It follows that $\Omega_0 = \{(0)\}$, $\Omega_1 = \{(0, 0)\}$, $\Omega_2 = \{(0, 0, 0)\}$ and $\Omega_3 = \{(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2)\}$. It follows that

More generally, let $n\ge 1$ and $(b_1, \ldots, b_n) \in \Omega_{n-1}$. Assume there exists $n_1$ elements with $b_n = 0$, $n_2$ elements with $b_n = 1$, and $n_3$ elements with $b_n = 2$. By definition of the set $K$, there exists

(1) $n_1+n_2$ elements $(b_1, \ldots, b_{n+1}) \in \Omega_{n}$ such that $b_{n+1} = 0$.

(2) $n_1+n_3$ elements $(b_1, \ldots, b_{n+1}) \in \Omega_{n}$ such that $b_{n+1} = 1$.

(3) $n_1$ elements $(b_1, \ldots, b_{n+1}) \in \Omega_{n}$ such that $b_{n+1} = 2$.

It follows that $\# \Omega_{n} = 3n_1+n_2+n_3$. Similarly, one can obtain a description of each set $\Omega_n, \Omega_{n+1}$ and $\Omega_{n+2}$. This will be summarized in Table 1.

Therefore,

3.1.   Markov chain

A family $({\mathsf X}_0, {\mathsf X}_1, \ldots)$ of random variables is called a Markov chain if, for a given $x_{n_0}$, the variables $({\mathsf X}_0, {\mathsf X}_1, \ldots, {\mathsf X}_{n_0-1})$ and $({\mathsf X}_{n_0+1}, \ldots, )$ are independent of each other. Therefore, the natural and easier way to describe a Markov chain is to specify, for each $n$, the distribution of ${\mathsf X}_{n-1}$ conditioned on the value of ${\mathsf X}_n$. Consider the following Markov chain:

(1) $B_1 = B_2 = B_3 = 0.$

(2) If $B_i = 0$, then ${\mathbb P}(B_{i+1} = 1) = p$, ${\mathbb P}(B_{i+1} = 2) = q$ and ${\mathbb P}(B_{i+1} = 0) = 1-p-q$.

(3) If $B_i = 1$, then ${\mathbb P}(B_{i+1} = 0) = 1$.

(4) If $B_i = 2$, then ${\mathbb P}(B_{i+1} = 1) = 1$.

In particular, we have the following transitive probabilities (see Table 2), which may be represented visually using a transition graph (Figure 2):

A Markov chain that is irreducible (so it can get from any state to any other state with positive probability) and aperiodic (as is any chain that contains a state with positive probability of moving back to itself) will have a limiting distribution. This means that $\lim\limits_{n\to \infty} {\mathbb P}(B_n = 0)$ and $\lim\limits_{n\to \infty} {\mathbb P}(B_n = 1)$ exist. Moreover, one has

It follows that

Now, consider the event $A_n = \big\{ B_{n+1} = B_{n+2} = 0 \big\}$ then

Then, $\lim_{n} {\mathbb P}(A_n)$ exists and depends of $p$ and $q$. We denote $\lim\limits_{n\to \infty} {\mathbb P}(B_{n} = 0) = \alpha_0$ and $\lim\limits_{n\to\infty} {\mathbb P}(B_{n} = 1) = \alpha_1$; then using (3.1), we get

It follows that

Example 3.1. Take $p = 0.25$ and $q = 0.125$ then

In Table 3 we will calculate the first few probabilities of the event $A_n$.

So, after only $11$ steps in the chain, the probability ${\mathbb P}(A_n)$ does not change from step to step. However, one can compute this limit using the parameters $p$ and $q$. Indeed, denote $\lim\limits_{n\to\infty} {\mathbb P}(B_{n} = 0) = \alpha_0$ and $\lim\limits_{n\to\infty} {\mathbb P}(B_{n} = 1) = \alpha_1$ then, using (3.2), we get

and then $\lim\limits_{n\to\infty} {\mathbb P}(A_n) = 0.39 \alpha_0 + 0.625 \alpha_1 = 0.4162.$

Remark 3.1. We have

Hence, every time we see a $2$ in the sequence $b_4, \ldots, b_n$, we have a probability factor of $q$, then the $1$ that follows the $2$ happens with probability one, and then the $0$ that follows the $1$ happens with probability one. If we see a $0$ that follows a $0$, we have a probability factor of $1- p-q$.

Let $s_2$ and $s_1$ be the number of 2's and 1's in $(b_4, \ldots, b_n, 0, 0)$, respectively. Hence, the number of 0's is $n+2-3 -(s_1+s_2)$. Moreover, using Remark 3.1 and the assumption of the event $A_n: = \{ B_{n+1} = B_{n+2} = 0\}$, we have

(1) the number of 1's preceded by a $2$ is $s_2$ and then the number of 1's preceded by a $0$ is $s_1-s_2$;

(2) the number of 0's preceded by a $1$ is $s_1$ and then the number of 0's preceded by a $0$ is $n-1 -(s_1+s_2) - s_1 = n-s_2-2s_1-1.$

3.2.   Distribution of $(B_1, B_2, \ldots, B_n)$

In this section, we will study the distribution of $(B_1, B_2, \ldots, B_n)$ conditioned on $B_{n+1} = B_{n+2} = 0$. Observe, if $b_1 = b_2 = b_3 = 0$, that

Lemma 3.1. Let ${\mathsf p}\in (0, 1)$ the golden probability; that is, the unique solution of $f(x) = x+\sqrt{x}(x+1)-1 = 0$. For ${\mathsf q} = {\mathsf p}^{3/2}$, we have

and then

Proof. First, observe that $f(x) = x+\sqrt{x}(x+1)-1$ has a unique solution in $(0, 1)$ (since $f$ is a continuous and increasing function with $f(0)f(1) < 0)$. Now, using (3.5) and our choice of ${\mathsf p}$ and ${\mathsf q}$, we get

which does not depends of $s_1$ and $s_2$, since $\sqrt{ {\mathsf p}} = 1- {\mathsf p}- {\mathsf q}$. It follows that

and then each of the elements of $\Omega_{n-1}$ is equally likely to appear. This implies that

as required for the Eq (3.6). Now, using the Eq (3.7), we get

Recall that ${\mathbb P}(A_n) = (1- {\mathsf p}- {\mathsf q})^2 {\mathbb P}(B_{n} = 0) +(1- {\mathsf p}- {\mathsf q}) {\mathbb P}(B_{n} = 1)$. It follows from (3.3) that

Using the fact that $f({\mathsf p}) = {\mathsf p}+\sqrt{ {\mathsf p}}({\mathsf p}+1)-1 = 0$, we get $1- {\mathsf p}- {\mathsf q} = \sqrt{ {\mathsf p}}$ and then

□ The proof of Theorem 1.2 is a direct consequence of the Lemma and then, we get

Remark 3.2. (1) Recall the Binet formula, with $a = b = c = 1$, introduced in the introduction

and then $\lim\limits_{n\to\infty}\frac{ {\mathsf T}_n }{\phi^{n+1}} = \theta^{-1}$. Now, observe that

It follows that $\phi^{-2}\in (0, 1)$ is a solution of $f(x) = x+\sqrt{x}(x+1)-1 = 0$ which implies that ${\mathsf p} = \phi^{-2} = 0.295597\ldots$ and then ${\mathsf q} = 0.160713\ldots.$. It follows that

where $\theta = 5.470354\ldots.$. From Theorem 1.2, we get $\lim\limits_{n\to\infty}\frac{ {\mathsf T}_n }{\phi^{n+1}} = \theta^{-1}$.

(2) The technique used in this section cannot be applied to study the $k$-Fibonacci-like sequence. We ask how this method can be suitably modified in order to construct an adequate Markov chain encapsulating the entire $k$-Fibonacci-like sequence $(G_{k, n})_n$ and then give the limiting behavior of this sequence.

4.   Conclusions

In this work, we studied the probability of return for random walks on Z, whose increment is given by the k-Fibonacci-like sequence $(G_{kn})$ (Theorem 1.1). In particular, we have ${\mathbb P}({\mathsf N}) = 0$, where ${\mathsf N}$ is the set of walks returning to zero infinitely many times. For this, we were interested to describing geometrically the set ${\mathsf N}$ by computing its fractal dimension. We studied, in Section 3, the Tribonacci sequence $({\mathsf T}_n)$. We considered an irreducible and aperiodic Markov chain with finite state $(B_n)$. We proved, conditional on $B_{n+1} = B_{n+2} = 0$, that the values of $(B_1, \ldots, B_n)$ are uniform over a set $\Omega_{n-1}$ with $\#\Omega_{n-1} = {\mathsf T}_{n-1}$. This forces the size of $\Omega_{n-1}$ to grow at a precisely controlled rate and yields the limiting behavior of the sequence ${\mathsf T}_n$.

Acknowledgments

The authors extend their appreciation to the Deanship of Scientific Research, Vice Presidency for Graduate Studies and Scientific Research at King Faisal University, Saudi Arabia, for financial support under the annual funding track [KFU241631].

Conflict of interest

The authors declare no conflit of interest.