On Fibonacci-Like Sequences

Le Anh Vinh School of Mathematics University of New South Wales Sydney 2052 NSW Australia

                    vinh@maths.unsw.edu.au

Abstract In this note, we study Fibonacci-like sequences that are defined by the recurrence S_{k} = a, S_{k+1} = b, S_{n+2} ≡ S_{n+1} + S_{n} (mod n + 2) for all n ≥ k, where k, a, b ∈ ℕ, 0 ≤ a < k, 0 ≤ b < k + 1, and (a, b) ≠ (0, 0). We will show that the number α = 0.S_{k}S_{k+1}S_{k+2} ⋯ is irrational. We also propose a conjecture on the pattern of the sequence {S_{n}}_{n≥k}.

1 Introduction

Given a sequence of natural numbers a_{1}, a_{2}, …, the question of determining the irrationality of the number α = 0.a_{1}a_{2} ⋯ is a classical and interesting question. For example, if a_{1}, a_{2}, … is the sequence of all prime numbers, then α is irrational ([5]). Another well-known example is the set of generalized Mahler sequences. Let m ≥ 1, h ≥ 2 be integers, and

(m)_{h} = m_{1}h^{r−1} + m_{2}h^{r−2} + ⋯ + m_{r}

for some integer r > 0 and 0 ≤ m_{i} < h for all 1 ≤ i ≤ r. Mahler [6] showed that for t ≥ 2 then the number

a(t) = 0.(t^{0})_{10}(t^{1})_{10}(t^{2})_{10} ⋯

is irrational. Bundschuh [4] generalized this result to arbitrary bases. More precisely, he showed that for any t, r ≥ 2 then the number

a_{r}(t) = 0.(t^{0})_{r}(t^{1})_{r}(t^{2})_{r} ⋯

is irrational. Readers can find several proofs of this result in [7, 9]. In the most general form, one studies the number

a_{r}(t) = a_{r}^{(n_{i})}(t) = 0.(t^{n_{0}})_{r}(t^{n_{1}})_{r}(t^{n_{2}})_{r} ⋯

for given r, t ≥ 2 and sequence (n_{i})_{i≥0} of non-negative integers. In [10], Shan and Wang showed that a_{r}(t) is irrational if (n_{i}) is an unbounded sequence. Several criteria for irrationality of a_{r}(t) for bounded (n_{i}) were obtained by Sander [8], and Shorey and Tijdeman [11]. Motivated by these papers, we will study an analogous result for some Fibonacci-like sequences.

Recall that the Fibonacci sequence is defined by the following recurrence:

F_{0} = 0, F_{1} = 1, F_{n+2} = F_{n+1} + F_{n} for all n ≥ 0.

In this note, we will study some properties of Fibonacci-like sequences that are defined by the following recurrence:

S_{k} = a, S_{k+1} = b, S_{n+2} ≡ S_{n+1} + S_{n} (mod n + 2 )  for all  n ≥ k,  (1)

for some k, a, b ∈ ℕ, 0 ≤ a < k and 0 ≤ b < k+1. For any triple (k, a, b) ∈ ℕ^{3} with 0 ≤ a < k and 0 ≤ b < k + 1, we denote S_{a,b}^{k} = {S_{a,b}^{k}(n)}_{n=k}^{∞} the sequence defined by recurrence (1).

The main result of this note is the following theorem.

Theorem 1. Suppose that a, b, k are natural numbers with 0 ≤ a < k, 0 ≤ b < k + 1. Then

α_{a,b}^{k} = 0.S_{a,b}^{k}(k)S_{a,b}^{k}(k + 1)S_{a,b}^{k}(k + 2) …  (2)

is irrational. Here expression (2) means that the decimal expansion of α_{a,b}^{k} is obtained by the concatenation of the integers S_{a,b}^{k}(n) written in decimal form.

It is worth noticing that most of papers inspired by Mahler deal with exponentially increasing sequences, while S_{a,b}^{k} is always less than n. Furthermore, while the Fibonacci sequence is well-known and has been studied extensively in the literature, it seems that the sequence S_{a,b}^{k} has not been studied before. The only reference we found about these sequences refers to S_{0,1}^{0}. This sequence is known as sequence \underline{A056542} in Sloane’s Online Encyclopedia of Integer Sequences [12].

2 Irrationality

In order to give a proof for Theorem 1, we first need some lemmas.

Lemma 2. Suppose that a, b, k ∈ ℕ such that 0 ≤ a < k, 0 ≤ b < k + 1, (a, b) ≠ (0, 0). Then the sequence S_{a,b}^{k} is not bounded.

Proof. Suppose that S_{a,b}^{k} is bounded for some a, b, k. Let M = max_{n≥k}{S_{a,b}^{k}(n)}. Then, for every n > 2M, we have S_{a,b}^{k}(n) = S_{a,b}^{k}(n − 1) + S_{a,b}^{k}(n − 2), since S_{a,b}^{k}(n − 1) ≤ M and S_{a,b}^{k}(n − 2) ≤ M. Thus, the sequence S_{a,b}^{k} eventually coincides with a usual linear recurrence sequence taking non-negative values. Since S_{a,b}^{k} is bounded it immediately follows that

S_{a,b}^{k}(n − 1) = S_{a,b}^{k}(n − 2) = 0.

By backward induction, we have S_{a,b}^{k}(n) = 0 for all n, which is a contradiction. This concludes the proof of the lemma.

Lemma 3. For any sufficiently large m, there exists n such that S_{a,b}^{k}(n) has exactly m digits. In other words, there exists n such that 10^{m−1} ≤ S_{a,b}^{k}(n) < 10^{m}.

Proof. From Lemma 2, the sequence {S_{a,b}^{k}(n)}_{n≥k} is unbounded. Hence there exists n such that S_{a,b}^{k}(n) ≥ 10^{m−1}. We choose n as small as possible. Then S_{a,b}^{k}(n−1), S_{a,b}^{k}(n−2) < 10^{m−1}. This implies that

S_{a,b}^{k}(n) ≤ S_{a,b}^{k}(n − 1) + S_{a,b}^{k}(n − 2) < 2 × 10^{m−1} < 10^{m}.

This concludes the proof of the lemma.

Using Lemma 2 and Lemma 3, we get the following proof of Theorem 1.

Proof. (of Theorem 1) Suppose that α_{a,b}^{k} is a rational number for some a, b, k. Then it has an eventually periodic decimal expansion. Thus we can write

α_{a,b}^{k} = 0.a_{1} … a_{s}b_{1} … b_{t}b_{1} … b_{t} …

We choose n large enough such that S_{a,b}^{k}(n) starts from a position after a_{s}. Then for any r ≥ n, the number α_{r} = S_{a,b}^{k}(r)S_{a,b}^{k}(r+1)S_{a,b}^{k}(r+2) … is periodic of period wt for any positive integer w. We choose m = vt for some large positive integer v such that 10^{m−1} > S_{a,b}^{k}(i) for all i ≤ n. From Lemma 3, there exists l such that S_{a,b}^{k}(l) has exactly m digits. We choose l to be as small as possible; then l > n.

If S_{a,b}^{k}(l − 1) = 0, then S_{a,b}^{k}(l − 2) = S_{a,b}^{k}(l) has exactly m digits, which is a contradiction. Hence 0 < S_{a,b}^{k}(l − 1) < 10^{m−1}. Similarly, we have 0 < S_{a,b}^{k}(l − 2) < 10^{m−1}. Hence

S_{a,b}^{k}(l) ≤ S_{a,b}^{k}(l − 2) + S_{a,b}^{k}(l − 1) < 2 × 10^{m−1},
S_{a,b}^{k}(l + 1) ≤ S_{a,b}^{k}(l − 1) + S_{a,b}^{k}(l) < 3 × 10^{m−1}.

Therefore, S_{a,b}^{k}(l + 1) has no more than m digits. We have two separate cases.

1. Suppose that S_{a,b}^{k}(l + 1) ≡ S_{a,b}^{k}(l − 1) + S_{a,b}^{k}(l) (mod l + 1) has m digits. But α_{l} = S_{a,b}^{k}(l)S_{a,b}^{k}(l + 1)S_{a,b}^{k}(l + 2) … is periodic of period m = vt so S_{a,b}^{k}(l + 1) = S_{a,b}^{k}(l). This implies that S_{a,b}^{k}(l − 1) = 0 which is a contradiction.

2. Suppose that S_{a,b}^{k}(l + 1) ≡ S_{a,b}^{k}(l − 1) + S_{a,b}^{k}(l) (mod l + 1) has less than m digits. Let p = S_{a,b}^{k}(l + 1). Since α_{l} = S_{a,b}^{k}(l)S_{a,b}^{k}(l + 1)S_{a,b}^{k}(l + 2) … is periodic of period m = vt so S_{a,b}^{k}(l) = p ∗ q for some q where p ∗ q denotes the concatenation of p and q. We have

S_{a,b}^{k}(l + 2) ≤ S_{a,b}^{k}(l + 1) + S_{a,b}^{k}(l) < 10^{m−1} + 2 × 10^{m−1} < 3 × 10^{m−1}.

So S_{a,b}^{k}(l + 2) has no more than m digits. We have two subcases.

(a) Suppose that S_{a,b}^{k}(l + 2) has exactly m digits. Then by the periodicity of α_{l} we have S_{a,b}^{k}(l)S_{a,b}^{k}(l + 1)S_{a,b}^{k}(l + 2) = p ∗ q ∗ p ∗ q ∗ p. If S_{a,b}^{k}(l) + S_{a,b}^{k}(l + 1) ≥ l + 2 then

S_{a,b}^{k}(l) + S_{a,b}^{k}(l + 1) < l + 10^{m−1} < l + 2 + 10^{m−1},

which implies that S_{a,b}^{k}(l + 2) < 10^{m−1} which is a contradiction. Hence

S_{a,b}^{k}(l) + S_{a,b}^{k}(l + 1) < l + 2.

This implies that q ∗ p = S_{a,b}^{k}(l + 2) = S_{a,b}^{k}(l) + S_{a,b}^{k}(l + 1) = p ∗ q + p. Suppose that p ∗ q = 10^{h}p + q and q ∗ p = 10^{z}q + p. Then q(10^{z} − 1) = 10^{h}p. Thus, 10^{h} | q. But p ∗ q = 10^{h}p + q so q < 10^{h}. Hence q = 0 and p = 0 which is a contradiction.

(b) Suppose that S_{a,b}^{k}(l + 2) has less than m digits. Then we can replace k by l + 1. And we choose l′ to be the smallest l′ > l such that S_{a,b}^{l}(l′) has exactly m digits. Apply the above argument for the new sequence S_{a,b}^{l} until either we come up with a contradiction or we can choose l′ large enough such that l′ +1 > 3×10^{m−1}. But in this case

S_{a,b}^{k}(l′ + 1) ≤ S_{a,b}^{k}(l′ − 1) + S_{a,b}^{k}(l′) < 3 × 10^{m−1} < l′ + 1.

So S_{a+b}^{k}(l′ + 1) has exactly m digits. And we go to the case 1 which implies a contradiction.

This concludes the proof of the theorem.

We close this section by an open question.

Open Problem 1. For a, b, k are natural numbers with 0 ≤ a < k, 0 ≤ b < k + 1. Is α_{a,b}^{k} an algebraic or transcendental number?

3 Occurrence of zeros

By examining several sequences for small values of a, b and k, we notice a curious property of the sequence S_{a,b}^{k}: this sequence always contains many zeros. We are unable to prove this statement. Precisely, we propose the following conjecture.

Conjecture 4. Let a, b, k be natural numbers with 0 ≤ a < k, 0 ≤ b < k + 1. Then the sequence S_{a,b}^{k} contains infinitely many zero elements.

Suppose that the sequence S_{a,b}^{k} contains only finitely many zero elements for some a, b, k. Let v be the largest index such that S_{a,b}^{k}(v) = 0. Let c = S_{a,b}^{k}(v + 1) and d = S_{a,b}^{k}(v + 2). Then the sequence S_{c,d}^{v+1} contains no zero element. Therefore the conjecture is equivalent to the statement “there exists n such that S_{a,b}^{k}(n) = 0 for any a, b, k”.

If Conjecture 4 holds, let v_{k}(a, b) be the index of the first zero element in sequence S_{a,b}^{k}. We define

v_{k} = max_{0≤a<k,0≤b<k+1} v_{k}(a, b).

For any 0 ≤ a < k and 0 ≤ b < k + 1 then S_{a,b}^{k} = {a} ∪ S_{b,c}^{k+1} for some 0 ≤ c < k + 2. Thus, v_{k} ≤ v_{k+1} for any k. Furthermore, v_{v_{k}+1} ≥ v_{k} + 1 > v_{k} for any k. Hence

lim_{k→∞} v_{k} = ∞.

Using computer, we computed some values of the sequence {v_{k}}_{k∈ℕ}

{v_{k}}_{k≥1} = {28, 28, 108, 108, 130, 130, 184, 184, 184, 1523, 1523, …}.

4 Acknowledgment

The author would like to thank the referee for giving many useful comments which helped improve the presentation of this note, as well as pointing out some papers related to the work.

References

[1] M. Amou, Approximation to certain transcendental decimal fractions by algebraic numbers, J. Number Theory 37 (1991), 231–241.

[2] P. G. Becker, Exponential diophantine equations and the irrationality of certain real numbers, J. Number Theory 39 (1991), 108–116.

[3] P. G. Becker and J. W. Sander, Irrationality and codes, Semigroup Forum 51 (1995), 117–124.

[4] P. Bundschuh, Generalization of a recent irrationality result of Mahler, J. Number Theory 19 (1984), 248–253.

[5] N. Hegyvari, On some irrational decimal fractions, Amer. Math. Monthly 100 (1993), 779–780.

[6] K. Mahler, On some irrational decimal fractions, J. Number Theory 13 (1981), 268–269.

[7] H. Niederreiter, On an irrationality theory of Mahler and Bundschuh, J. Number Theory 24 (1986), 197–199.

[8] J. W. Sander, Irrationality criteria for Mahler’s numbers, J. Number Theory 52 (1995), 145–156.

[9] Z. Shan, A note on irrationality of some numbers, J. Number Theory 25 (1987), 211–212.

[10] Z. Shan and E. T. H. Wang, Generalization of a theorem of Mahler, J. Number Theory 32 (1989), 111–113.

[11] T. N. Shorey and R. Tijdeman, Irrationality criteria for numbers of Mahler’s type, in Y. Motohashi, ed., Analytic Number Theory, London Mathematical Lecture Note Series 247, Cambridge, 1997, pp. 343–351.

[12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically

at http://www.research.att.com/~njas.

[13] T. Vijayaraghavan, On the irrationality of a certain decimal, Proc. Indian Acad. Sci. Sect. A 10 (1939), 341.

2000 Mathematics Subject Classification: 05A15. Keywords: Fibonacci sequence, irrationality, Mahler-type problem.

(Concerned with sequence \underline{A056542}.)

Received October 21 2005; revised version received November 28 2007. Published in Journal of Integer Sequences, November 28 2007.

Return to Journal of Integer Sequences home page.