On Some Combinations of Non-Consecutive Terms of a Recurrence Sequence

Eva Trojovská Department of Mathematics Faculty of Science University of Hradec Králové Czech Republic

                 eva.trojovska@uhk.cz

Abstract

Let (G_{m})_{m≥0} be an integer linear recurrence sequence (satisfying some weak technical conditions) and let x ≥ 1 be an integer. In this paper, among other things, we are interested in non-consecutive combinations xG_{n+a} + G_{n} that belong to the sequence (G_{m})_{m≥0} for infinitely many positive integers n. In this case, we make explicit an upper bound for x that depends only on a and the zeros of the characteristic polynomial of this recurrence (this generalizes previous papers of Trojovský). As an application, we study the Fibonacci case.

1 Introduction

A sequence (G_{n})_{n≥0} is a linear recurrence sequence with coefficients c_{0}, c_{1}, …, c_{k−1}, with c_{0} ≠ 0, if

G_{n+k} = c_{k−1}G_{n+k−1} + ⋯ + c_{1}G_{n+1} + c_{0}G_{n},  (1)

for all positive integers n. A recurrence sequence is therefore completely determined by the initial values G_{0}, G_{1}, …, G_{k−1}, and by the coefficients c_{0}, c_{1}, …, c_{k−1}. The integer k is called the order of the linear recurrence. The characteristic polynomial of the sequence (G_{n})_{n≥0} is given by

ψ(x) = x^{k} − c_{k−1}x^{k−1} − ⋯ − c_{1}x − c_{0}.

It is well-known that for all n we have

G_{n} = g_{1}(n)α_{1}^{n} + ⋯ + g_{ℓ}(n)α_{ℓ}^{n},  (2)

where α_{j} is a zero of ψ(x) and g_{j}(x) is a polynomial over a certain number field, for j = 1, …, ℓ. In this paper, we consider only integer recurrence sequences, i.e., recurrence sequences whose coefficients and initial values are integers. Hence, g_{j}(n) is an algebraic number, for all j = 1, …, ℓ, and n ∈ ℤ.

In this paper we explore a problem that is related to papers [1, 2, 4, 6, 7]. Possibly the most famous recurrence sequence is the Fibonacci sequence (F_{n})_{n≥0} defined by the recurrence F_{n+1} = F_{n} + F_{n−1} (n ≥ 1) with initial values F_{0} = 0 and F_{1} = 1. Its companion sequence is the sequence of Lucas numbers (L_{n})_{n≥0} that are defined by the same recurrence but with initial values L_{0} = 2 and L_{1} = 1.

The Fibonacci numbers are known for their amazing properties (see [3] for the history, properties, and rich applications of the Fibonacci sequence and some of its variants). Among several attractive algebraic identities involving these numbers, we point out the identities of the form

xF_{n+a} + F_{n} = F_{n+b}.

For instance, when a = 1, Trojovský [6] proved that x = 1 and x = 2 are the only values providing identities. A question arose: what happens if a > 1? Are there other identities? The answer is Yes, as for example we have

11F_{n+5} + F_{n} = F_{n+10}.

Thus, the aim of this work is to combine some Diophantine tools (asymptotic estimates and Galois theory) in order to study the possibilities of existence of such identities in the case of a general linear recurrence. In particular, we show that it is possible to obtain an upper bound for x in the case when xG_{n+a} + G_{n} belongs to the sequence (G_{m})_{m≥0} for infinitely many integers m. This upper bound is effective and can be made explicit by means of a and the recurrence sequence. More precisely, our main result is the following

Theorem 1. Let (G_{n})_{n≥0} be an integer linear recurrence (of order at least 2) such that its characteristic polynomial ψ(x) has a simple positive zero that is the only zero lying outside the unit circle. If x ≥ 1 is an integer such that xG_{n+a} + G_{n} belongs to (G_{m})_{m≥0} for infinitely many integers n, then

x < \frac{2}{|β|^{a}} ,  (3)

where ψ(β) = 0 and |β| := max_{ψ(z)=0,|z|≤1} |z|.

Let us give a brief overview of our strategy for proving Theorem 1. First, by supposing that xG_{n+a} + G_{n} = G_{t(n)}, we prove that t(n) = n + b, for some integer b (this is done by using asymptotic results for G_{n}). Next, we use the asymptotic formula for G_{n+t}/G_{n} (when t ∈ {a, b}) to obtain the equation xα^{a} + 1 = α^{b}, where α is the dominant root of the sequence (G_{m})_{m≥0}. Since α > 1, the right-hand side of the previous identity can be very large. However, by conjugating by some convenient automorphism of the Galois group of the characteristic polynomial of the recurrence, we get |xβ^{a} + 1| = |β|^{b} < 1 (since we are supposing that the algebraic conjugates of α are inside the unit circle). In conclusion, we obtain an upper bound for x depending on β and a.

As an application of our Theorem 1, we completely solve the case when (G_{n})_{n≥0} = (F_{n})_{n≥0}. More precisely, we prove that

Theorem 2. If

xF_{n+a} + F_{n} = F_{m}  (4)

for infinitely many pairs (n, m) of positive integers, then there exists a nonnegative integer k such that

a = 2k + 1, m = n + 4k + 2 and x = L_{2k+1}.

In particular, we have the identity

L_{2k+1}F_{n+2k+1} + F_{n} = F_{n+4k+2},

for all n, k ≥ 0.

2 General recurrence sequences

2.1 Auxiliary facts

In this section, we recall some results that will be very useful for the proof of the above theorems. Let ψ(x) be the characteristic polynomial of a linear recurrence (G_{n})_{n≥0}. One can factor ψ(x) over the set of complex numbers as

ψ(x) = (x − α_{1})^{m_{1}}(x − α_{2})^{m_{2}} ⋯ (x − α_{t})^{m_{t}},  (5)

where α_{1}, …, α_{t} are distinct non-zero complex numbers (called the roots of the recurrence) and m_{1}, …, m_{t} are positive integers. The fundamental result in the theory of recurrence sequences asserts that there exist uniquely determined non-zero polynomials g_{1}, …, g_{ℓ} ∈ ℚ({α_{j}}_{j=1}^{t})[x], with deg g_{j} ≤ m_{j} − 1, for j = 1, …, t, such that

G_{n} = g_{1}(n)α_{1}^{n} + ⋯ + g_{t}(n)α_{t}^{n}, for all n.  (6)

For more details, see [5, Theorem C.1]. A root α_{j} of the recurrence is called the dominant root if |α_{j}| > |α_{i}|, for all j ≠ i ∈ {1, …, t}. The corresponding polynomial g_{j}(n) is called the dominant polynomial of the recurrence.

In the case of the Fibonacci and Lucas sequences, the above formula is known as Binet’s formula:

F_{n} = \frac{α^{n} − β^{n}}{α − β} and L_{n} = α^{n} + β^{n},  (7)

where α = (1+\sqrt{5})/2 (the golden number) and β = (1−\sqrt{5})/2 = −1/α. Now we prove some lemmas that are essential ingredients in what follows. Throughout the paper, α_{1} denotes the dominant root of (G_{n})_{n≥0}.

Lemma 3. Let ℓ be any integer and let (G_{n})_{n≥0} be any linear integer sequence satisfying the hypotheses of the Theorem 1. Then

lim_{n→∞} \frac{G_{n+ℓ}}{G_{n}} = α_{1}^{ℓ}.  (8)

Proof. The proof can be found in [6, Lemma 1].

Now we are ready to deal with the proofs of our results.

2.2 The proof of Theorem 1

Suppose that xG_{n+a} + G_{n} = G_{t(n)} for infinitely many n (say, n ∈ S), where t(n) ∈ ℤ, for all n. By dividing the relation xG_{n+a} + G_{n} = G_{t(n)} by G_{n}, we obtain x\frac{G_{n+a}}{G_{n}} + 1 = \frac{G_{t(n)}}{G_{n}}. Now, by letting n → ∞ (n ∈ S) in the previous relation, by using Lemma 3 and the fact that the algebraic conjugates of α_{1} lie on the unit circle, we get xα_{1}^{a} + 1 = lim_{n→∞,n∈S} α_{1}^{t(n)−n}. Then, since |α_{1}| > 1, the limit lim_{n→∞,n∈S} (t(n) − n) exists and is finite. However, t(n) − n is a sequence of integers, and so it must be constant for all sufficiently large n (in S). We let b denote that constant. Therefore, we can rewrite this identity as

α_{1}^{a}x + 1 = α_{1}^{b}.  (9)

Set 𝕂 = ℚ({α_{i}}_{i=1}^{t}). If β ∈ {α_{2}, …, α_{t}} and |β| = max{|α_{2}|, …, |α_{t}|}, then consider the automorphism σ in Gal(𝕂/ℚ) given by α_{1} ↦ β. By applying σ in the equality in (9), we obtain

β^{a}x + 1 = β^{b}.  (10)

Now taking absolute values, together with the reverse triangular inequality and by using the fact that |β| < 1, we arrive at

|β|^{a}x − 1 ≤ |β^{a}x + 1| = |β|^{b} < 1.

This implies that x < 2/|β|^{a}, which completes our proof.

3 The Fibonacci case

In the case of Fibonacci numbers, we use the previous theorem to obtain that if

xF_{n+a} + F_{n}

is a Fibonacci number for infinitely many integers n, then x < 2/|β|^{a} = 2α^{a}, since αβ = −1.

Now we can use the same machinery of the previous section to arrive at the Diophantine equation

xα^{a} + 1 = α^{b}.  (11)

Clearly, this implies that a < b (since x ≥ 1). Also, by using that x < 2α^{a}, we get

α^{b} = xα^{a} + 1 < 2α^{2a} + 1 < 3α^{2a} < α^{2a+3},

where we used the fact that α^{3} > 3. Thus, b < 2a + 3. The case a = 1 was already treated in [6, Theorem 2]. If a = 2, then we have that 1 ≤ x < 2α^{2} < 6 and 2 < b < 7. By using a simple Mathematica routine, we obtain that there is no solution to

xα^{2} + 1 = α^{b}

in the range 1 ≤ x ≤ 5 and 3 ≤ b ≤ 6. Thus, we may suppose that a > 2.

Now let us conjugate the relation in (11) by the Galois automorphism α ↦ β. Hence, we have

xβ^{a} + 1 = β^{b}.  (12)

By subtracting (11) and (12), we obtain

x(α^{a} − β^{a}) = α^{b} − β^{b},

which yields xF_{a} = F_{b}, by Binet’s formula. This implies that F_{a} | F_{b} and so a | b. However, a < b < 2a + 3 ≤ 3a (this last inequality holds because a ≥ 3) and therefore b = 2a. Thus, x = F_{b}/F_{a} = F_{2a}/F_{a} = L_{a}. Now it remains to prove that a is an odd number. In fact, by (11), we have

L_{a}α^{a} + 1 = α^{2a}

and by Binet’s formula

α^{2a} = L_{a}α^{a} + 1 = (α^{a} + β^{a})α^{a} + 1 = α^{2a} + (αβ)^{a} + 1.

Thus,

0 = (αβ)^{a} + 1 = (−1)^{a} + 1

implying that a is odd. The result is proved.

4 Conclusion

In this paper, we proved that if we have a linear recurrence sequence (G_{n})_{n≥0} satisfying some weak technical conditions (related to its roots) and if we have an identity of the form xG_{n+a} +G_{n} = G_{m} valid for infinitely many integers pairs (n, m), then the value of x must be bounded by 2/|β|^{a}, where β is the second largest root (in absolute value) of the recurrence. This result provides a very efficient way of finding possible identities, since this “second largest root” can be bounded (or even found) in an effective way. As an application, we worked on the case of Fibonacci numbers and we determined all identities in this case. In particular, we proved that x is a Lucas number with odd index.

5 Acknowledgement

I wish to thank to an annonymous reviwer for his/her constructive critisms and I thank for the support the Specific research 2018/No. 2101 of University of Hradec Králové.

References

[1] J. J. Bravo and F. Luca, Coincidences in generalized Fibonacci sequences, J. Number Theory 133 (2013), 2121–2137.

[2] L. Carlitz and R. Scoville, Partially ordered sets associated with Fibonacci representations, Duke Math. J. 40 (1973), 511–524.

[3] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, 2001.

[4] D. Marques, The proof of a conjecture concerning the intersection of k-generalized Fibonacci sequences, Bull. Brazilian Math. Soc. 44 (2013), 455–468.

[5] T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations. Cambridge Tracts in Mathematics 87, Cambridge University Press, 1986.

[6] P. Trojovský, On some combinations of terms of a recurrence sequence, Chaos Solitons Fractals 82 (2016), 34–37.

[7] P. Trojovský, On some combinations of k-nacci numbers, Chaos Solitons Fractals 85 (2016), 135–137.

2010 Mathematics Subject Classification: Primary 11D61; Secondary 11B39. Keywords: combination, recurrence sequence, characteristic polynomial, Fibonacci number.

(Concerned with sequence \underline{A000045}.) Received February 19 2018; revised version received March 11 2018. Published in Journal of Integer Sequences, March 12 2018. Return to Journal of Integer Sequences home page.