Concatenations with Binary Recurrent Sequences

William D. Banks Department of Mathematics University of Missouri Columbia, MO 65211 USA

               bbanks@math.missouri.edu

Florian Luca Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58089 Morelia, Michoacán México

                 fluca@matmor.unam.mx

Abstract

Given positive integers A_{1}, …, A_{t} and b ≥ 2, we write \overline{A_{1} ⋯ A_{t}}_{(b)} for the integer whose base-b representation is the concatenation of the base-b representations of A_{1}, …, A_{t}. In this paper, we prove that if (u_{n})_{n≥0} is a binary recurrent sequence of integers satisfying some mild hypotheses, then for every fixed integer t ≥ 1, there are at most finitely many nonnegative integers n_{1}, …, n_{t} such that \overline{|u_{n_{1}}| ⋯ |u_{n_{t}}|}_{(b)} is a member of the sequence (|u_{n}|)_{n≥0}. In particular, we compute all such instances in the special case that b = 10, t = 2, and u_{n} = F_{n} is the sequence of Fibonacci numbers.

1 Introduction

A result of Senge and Straus [24, 25] asserts that if b_{1}, b_{2} ≥ 2 are multiplicatively independent integers, there are at most finitely many positive integers with the property that the sum of the digits in each of the two bases b_{1} and b_{2} lies below any prescribed bound. An effective version of this statement is due to Stewart [28], who gave a lower bound on the overall sum of the digits of n in base b_{1} and in base b_{2}. A somewhat more general version of Stewart’s result has been obtained by Luca [16].

A variety of arithmetical questions about integers whose base-b digits satisfy certain restrictions has been considered by many authors; see, for example, [1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 16, 18, 19, 27] and the references contained therein. Here, we consider integers whose base-b digits are formed by concatenating (absolute values of) terms in a binary recurrent sequence.

Let (u_{n})_{n≥0} be a binary recurrent sequence of integers; i.e., a sequence of integers satisfying the recurrence relation

u_{n+2} = ru_{n+1} + su_{n}  (n ≥ 0),  (1)

where r and s are nonzero integers with r^{2} + 4s ≠ 0. It is well known that if α and β are the roots of the equation x^{2} − rx − s = 0, then u_{n} = cα^{n} + dβ^{n} holds for all n ≥ 0, where c and d are constants given by

c = \frac{−βu_{0} + u_{1}}{α − β} and d = \frac{αu_{0} − u_{1}}{α − β} .

Throughout the paper, we assume that (u_{n})_{n≥0} is nondegenerate (i.e., α/β is not a root of 1, and αβcd ≠ 0). Reordering the roots if necessary, we can further assume that |α| ≥ |β| and |α| > 1.

Let b ≥ 2 be a fixed integer base. Given positive integers A_{1}, …, A_{t}, we denote by \overline{A_{1} ⋯ A_{t}}_{(b)} the integer whose base-b representation is equal to the concatenation (in order) of the base-b representations of A_{1}, …, A_{t}. Thus, if l_{i} is the smallest positive integer such that A_{i} < b^{l_{i}}, we have

\overline{A_{1} ⋯ A_{t}}_{(b)} = b^{l_{2}+···+l_{t}}A_{1} + b^{l_{3}+···+l_{t}}A_{2} + ⋯ + b^{l_{t}}A_{t−1} + A_{t} .

We always assume that A_{1} ≠ 0, and in the special case that b = 10, we omit the subscript to simplify the notation.

In this paper, we study the set of positive integers |u_{n}|, where (u_{n})_{n≥0} is a binary recurrent sequence, that are the base-b concatenations of other numbers of the form |u_{n_{j}}|, j = 1, …, t. We show that if t ≥ 2 is fixed, then there are only finitely many instances of the equality

|u_{n}| = \overline{|u_{n_{1}}| ⋯ |u_{n_{t}}|}_{(b)}

provided that the sequence (u_{n})_{n≥0} satisfies certain mild hypotheses. Note that some assumptions are clearly needed in order to rule out certain obvious counterexamples; for instance, the result does not hold for the sequence u_{n} = b^{n} − 1, n ≥ 0, since the concatenation of any two or more terms produces another term of the same sequence.

Theorem 1. Let u_{n} = cα^{n} + dβ^{n} be a nondegenerate binary recurrent sequence of integers, and let b ≥ 2 be a fixed integer base. Assume that dim_{ℤ}⟨log α, log β, log b⟩ ≥ 2. Then for every fixed integer t ≥ 2, there are at most finitely many positive integers n for which the equality

|u_{n}| = \overline{|u_{n_{1}}| \underbrace{0 ⋯ 0}_{m_{1}} |u_{n_{2}}| \underbrace{0 ⋯ 0}_{m_{2}} ⋯ |u_{n_{t}}| \underbrace{0 ⋯ 0}_{m_{t}}} _{(b)}  (2)

holds for some nonnegative integers n_{1}, …, n_{t} and m_{1}, …, m_{t} with u_{n_{1}} ≠ 0.

Here, log(·) stands for any fixed determination of the natural logarithm function, and dim_{ℤ}⟨log α, log β, log b⟩ denotes the rank of (the free part of) the additive subgroup of ℂ generated by {log α, log β, log b}.

Although our proof of Theorem 1 is ineffective, this result can be seen as an extension of the aforementioned results of Senge and Straus [24, 25].

In some special cases, one can employ effective methods to completely determine all the solutions to an equation such as (2). Perhaps the best known example of a binary recurrent sequence is the Fibonacci sequence (F_{n})_{n≥0}, where F_{0} = 0 and F_{1} = 1, and (1) holds with r = s = 1. In this case, one has α = (1 + \sqrt{5})/2, β = −α^{−1}, c = 1/(α − β), and d = −c. For this special sequence, we obtain the following computational result:

Theorem 2. If (m, n, k) is an ordered triple of nonnegative integers with m > 0 and such that \overline{F_{m}F_{n}} = F_{k}, then F_{k} ∈ \{13, 21, 55\}.

Throughout the paper, we use the Vinogradov symbols ≪ and ≫, as well as the Landau symbol O, with the understanding that the implied constants are computable and depend at most on the given data.

2 Preliminaries

Let 𝕃 be an algebraic number field of degree D over ℚ. Denote by O_{𝕃} the ring of algebraic integers and by M_{𝕃} the set of places. For a fractional ideal I of 𝕃, let Nm_{𝕃}(I) be the usual norm; we recall that Nm_{𝕃}(I) = #(O_{𝕃}/I) if I is an ideal of O_{𝕃}, and the norm map is extended multiplicatively (using unique factorization) to all of the fractional ideals of 𝕃.

For a prime ideal P, we denote by ord_{P}(x) the order at which P appears in the ideal factorization of the principal ideal [x] generated by x in 𝕃.

For a place μ ∈ M_{𝕃} and a number x ∈ 𝕃, we define the absolute value |x|_{μ} as follows:

(i) |x|_{μ} = |σ(x)|^{1/D} if μ corresponds to a real embedding σ : 𝕃 → ℝ;

(ii) |x|_{μ} = |σ(x)|^{2/D} = |\overline{σ}(x)|^{2/D} if μ corresponds to some pair of complex conjugate embeddings σ, \overline{σ} : 𝕃 → ℂ;

(iii) |x|_{μ} = Nm_{𝕃}(P)^{−ord_{P}(x)/D} if μ corresponds to a nonzero prime ideal P of O_{𝕃}.

In the case (i) or (ii), we say that μ is real infinite or complex infinite, respectively; in the case (iii), we say that μ is finite.

The set of absolute values are well known to satisfy the following product formula:

∏_{μ∈M_{𝕃}} |x|_{μ} = 1,  for all x ∈ 𝕃^{∗}.  (3)

One of our principal tools is the following simplified version of a result of Schlickewei [22, 23], which is commonly known as the Subspace Theorem:

Theorem 3. Let 𝕃 be an algebraic number field of degree D. Let S be a finite set of places of 𝕃 containing all the infinite ones. Let {L_{1,μ}, …, L_{N,μ}} for μ ∈ S be linearly independent sets of linear forms in N variables with coefficients in 𝕃. Then, for every fixed 0 < ε < 1, the set of solutions x = (x_{1}, …, x_{N}) ∈ 𝕃^{N}\{0} to the inequality

∏_{μ∈S} ∏_{i=1}^{N} |L_{i,μ}(x)|_{μ} ≤ (max{|x_{i}| : i = 1, …, N})^{−ε}  (4)

is contained in finitely many proper linear subspaces of 𝕃^{N}.

Let S be a finite subset of M_{𝕃} containing all the infinite places. An element x ∈ 𝕃 is called a S-unit if |x|_{μ} = 1 for all μ ∉ S. An equation of the form

∑_{i=1}^{N} a_{i}x_{i} = 0,  (5)

where each a_{i} ∈ 𝕃^{∗}, is called an S-unit equation if each x_{i} is an S-unit; it is said to be nondegenerate if no proper subsum of the left hand side vanishes. It is clear that if x = (x_{1}, …, x_{N}) is a solution of the S-unit equation (5), and ρ is a S-unit in 𝕃^{∗}, then ρx = (ρx_{1}, …, ρx_{N}) is a also a solution of (5); in this case, the solutions x and ρx are said to be equivalent. We recall the following result of Schlickewei [21] (see also [8]) on S-unit equations:

Theorem 4. Let a_{1}, …, a_{N} be fixed numbers in 𝕃^{∗}. Then the S-unit equation (5) has only finitely many equivalence classes of nondegenerate solutions (x_{1}, …, x_{N}). Moreover, the number of such equivalence classes is bounded by a constant that depends only on N and the cardinality of S.

An immediate consequence of Theorem 4 is that if x = (x_{1}, …, x_{N}) is a solution of the S-unit equation (5), then the ratios x_{i}/x_{j} for 1 ≤ i < j ≤ N can assume only finitely many values.

We shall also need some estimates from the theory of lower bounds for linear forms in logarithms, both in the complex and the p-adic cases.

Let α_{1} and α_{2} be algebraic numbers. Put 𝕃 = ℚ[α_{1}, α_{2}], and let D be the degree of 𝕃 over ℚ. Let A_{1} and A_{2} be two positive integers such that

log A_{i} ≥ max \{h(α_{i}), \frac{| log α_{i}|}{D}, \frac{1}{D}\}  (i = 1, 2).  (6)

Here, for an algebraic number α whose minimal polynomial over ℤ is a ∏_{i=1}^{d}(X − α^{(i)}), we write h(α) for the logarithmic height of α, which is given by

h(α) = \frac{1}{d} (log |a| + ∑_{i=1}^{d} log (max\{1, |α^{(i)}|\})) .

Let b_{1} and b_{2} be positive integers, and put Λ = b_{2} log α_{2} − b_{1} log α_{1}. Finally, let

b′ = \frac{b_{1}}{D log A_{2}} + \frac{b_{2}}{D log A_{1}} .

The following result is Corollaire 2 on page 288 of [20], which gives an effective lower bound on the size of log |Λ|:

Theorem 5. Assume that α_{1} and α_{2} are real, positive, and multiplicatively independent. Then

log |Λ| ≥ −24.34D^{4} (max \{log b′ + 0.14, \frac{21}{D}, \frac{1}{2}\})^{2} log A_{1} log A_{2}.

We also need a p-adic lower bound on Λ, that is, an upper bound on the order at which a prime ideal P can appear in the factorization of the principal ideal generated by Λ_{1} = α_{1}^{b_{1}}−α_{2}^{b_{2}} inside O_{𝕃}. For this, let p be the prime number such that P | p (i.e., pℤ = P ∩ℤ), and let f be such that the finite field O_{𝕃}/P has p^{f} elements. Let g be the smallest positive integer such that P divides both α_{1}^{g} − 1 and α_{2}^{g} − 1. Assume further that A_{i} satisfies the inequality (6) as well as the inequality log A_{i} ≥ f(log p)/D, for i = 1, 2. The following result is an easy consequence of Corollaire 2 on page 315 of [4]:

Theorem 6. Assume that α_{1} and α_{2} are multiplicatively independent. Then

ord_{P} (Λ_{1}) ≤ \frac{24pgD^{5}}{f^{4}(p − 1)(log p)^{4}}
× (max \{log b′ + log log p + 0.4, \frac{10f log p}{D}, 10\})^{2} log A_{1} log A_{2}.

3 Proof of Theorem 1

Our proof of Theorem 1 also treats the (slightly more general) case in which we allow t = 1, but in this case we add the additional hypothesis that m_{1} ≥ 1 (clearly, this condition is needed to insure that the number of solutions to (2) is finite).

Since α/β is not a root of unity, at most one element of the sequence (u_{n})_{n≥0} is equal to 0. Hence, if u_{n_{i}} = 0 for some i in (2), then n_{i} is uniquely determined. Note that i ≠ 1. If this happens, then equation (2) can be viewed as an equation of the same form, but with t replaced by t − 1 (and with only 2t − 1 unknowns). Thus, to prove the theorem, it suffices to show that there at most finitely many solutions to (2) with u_{n_{i}} ≠ 0, i = 1, …, t.

Let 𝕃 = ℚ[α, β], and let S be the set of all infinite places of 𝕃 and all finite places that divide sb = −αβb. For a positive integer m, let ℓ_{b}(m) denote the number of the digits in the base-b representation of m.

Equation (2) is equivalent to

|u_{n}| = ∑_{i=1}^{t} |u_{n_{i}}|b^{s_{i}},  (7)

where

s_{i} = ∑_{j=i}^{t} m_{j} + ∑_{j=i+1}^{t} ℓ_{b}(|u_{n_{j}}|) (i = 1, …, t).

We remark that, if n = n_{i} for some i, it follows that t = 1 (since each u_{n_{i}} ≠ 0) and s_{1} = m_{1} = 0 (since b ≥ 2), which contradicts our assumption that m_{1} ≥ 1 when t = 1. Hence, n ≠ n_{i} for all i = 1, …, t. Now write (7) in the form

ε_{0}(cα^{n} + dβ^{n}) = ∑_{i=1}^{t} ε_{i} (cα^{n_{i}} + dβ^{n_{i}}) b^{s_{i}},  (8)

where ε_{i} ∈ {±1} for i = 0, …, t.

Suppose first that n_{i} > n − κ for some i ∈ {1, …, t}, where κ ≥ 0 is a constant to be specified later. From (7), we have that |u_{n}| ≥ |u_{n_{i}}|b^{s_{i}}. It is known that the estimate |u_{m}| = |α|^{m+O(log m)} holds for all positive integers m ≥ 2 (see Theorem 3.1 on page 64 in [26]). Moreover, if α is real, then |α| > |β|, and one has the estimate |u_{m}| = |α|^{m+O(1)}. Therefore, since |α| > 1, the following bound holds if n_{i} > n − κ:

max\{n_{i} − n, s_{i}\} ≪ \{ \begin{matrix}1, & if α ∈ ℝ; \\ log n, & if α ∉ ℝ (i.e., α = \overline{β}). \end{matrix}  (9)

Next, we show that if n_{i} ≤ n − κ for every i = 1, …, t, then there exists an index i ∈ {1, …, t} for which the following bound holds:

max{n − n_{i}, s_{i}} ≪ 1.  (10)

To do this, we first observe that (8) is an S-unit equation with N = 2t + 2 terms, coefficients (a_{1}, …, a_{N}) = (c, d, −c, −d, …, −c, −d), and the S-unit unknowns x = (x_{1}, …, x_{N}) = (ε_{0}α^{n}, ε_{0}β^{n}, ε_{1}α^{n_{1}}b^{s_{1}}, …, ε_{t}β^{n_{t}}b^{s_{t}}).

If the S-unit equation (8) is nondegenerate, then x_{1}/x_{2} = (α/β)^{n} can assume only finitely many values; since α/β is not a root of unity, it follows that n can take at most finitely many values.

On the other hand, if the S-unit equation (8) is degenerate, let E_{1} and E_{2} be two (not necessarily distinct) nondegenerate subequations of (8) that contain the unknowns x_{1} = ε_{0}α^{n} and x_{2} = ε_{0}β^{n}, respectively. Clearly, E_{1} and E_{2} can be chosen in at most finitely many ways. The preceding argument shows that n can assume only finitely many values if the unknowns x_{1} and x_{2} both lie in E_{1} or both lie in E_{2}. Therefore, we may assume that E_{1} does not contain x_{2}, and E_{2} does not contain x_{1}. We now distinguish the following cases:

(i) E_{1} contains an unknown of the form x_{2i+1} = ε_{i}α^{n_{i}}b^{s_{i}} for some i ≥ 1 and E_{2} contains an unknown of the form x_{2j} = ε_{j}β^{n_{j}}b^{s_{j}} for some j ≥ 2.

In this case, both x_{1}/x_{2i+1} = ±α^{n−n_{i}}b^{−s_{i}} and x_{2}/x_{2j} = ±β^{n−n_{j}}b^{−s_{j}} can assume only finitely many values. Since dim_{ℤ}⟨log α, log β, log b⟩ ≥ 2, it follows that either the pair (α, b) or the pair (β, b) is multiplicatively independent; thus, either max{n−n_{i}, s_{i}} ≪ 1 or max{n − n_{j}, s_{j}} ≪ 1.

(ii) E_{1} contains only unknowns of the form x_{2i} = ε_{i}β^{n_{i}}b^{s_{i}} with i ≥ 2 (except for x_{1}) and E_{2} contains only unknowns of the form x_{2j+1} = ε_{j}α^{n_{j}}b^{s_{j}} with j ≥ 1 (except for x_{2}).

For each choice of the indices i and j, both x_{1}/x_{2i} = ±α^{n}β^{−n_{i}}b^{−s_{i}} and x_{2}/x_{2j+1} = ±β^{n}α^{−n_{j}}b^{−s_{j}} can have at most finitely many values. Since we may assume that n takes infinitely many values (otherwise, there is nothing to prove), it follows that there exist numbers n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, and s_{j}^{∗} such that both relations

\begin{aligned}α^{n}β^{−n_{i}}b^{−s_{i}} & = α^{n^{∗}}β^{−n_{i}^{∗}}b^{−s_{i}^{∗}}, \\ β^{n}α^{−n_{j}}b^{−s_{j}} & = β^{n^{∗}}α^{−n_{j}^{∗}}b^{−s_{j}^{∗}}, \end{aligned}  (11)

hold for arbitrarily large values of n. Among all possible choices for the quintuple (n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, s_{j}^{∗}) of such numbers, we fix one for which n_{i}^{∗} is as small as possible; thus, n_{i} ≥ n_{i}^{∗} whenever the relations (11) hold.

Since there are only finitely many possibilities for E_{1} and E_{2} and (once these are fixed) for the indices i and j, we obtain in this way a finite list of such quintuples (n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, s_{j}^{∗}). Hence, the constant κ can be initially chosen such that the inequality κ > max{n^{∗} − n_{i}^{∗}, n^{∗} − n_{j}^{∗}} holds in all cases.

Now let E_{1}, E_{2}, i, and j be fixed, and suppose that the relations (11) hold with n > n^{∗}. Taking logarithms, we obtain that

(n − n^{∗}) log α = (n_{i} − n_{i}^{∗}) log β + (s_{i} − s_{i}^{∗}) log b,
(n − n^{∗}) log β = (n_{j} − n_{j}^{∗}) log α + (s_{j} − s_{j}^{∗}) log b.

Let v_{1} = (n_{i} − n_{i}^{∗})/(n − n^{∗}) and v_{2} = (n_{j} − n_{j}^{∗})/(n − n^{∗}), and note that both numbers are rational. Since we are assuming that n_{i} ≤ n − κ for i = 1, …, t, it follows that

n^{∗} − n_{i}^{∗} < κ ≤ n − n_{i},

which implies that v_{1} < 1. Similarly, v_{2} < 1. Since n_{i} ≥ n_{i}^{∗} by our choice of the quintuple (n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, s_{j}^{∗}), we also see that v_{1} ≥ 0. These statements together imply that v_{1}v_{2} ≠ 1, which is all we need. From the preceding relations, we obtain that

log α = v_{1} log β + w_{1} log b = v_{1}(v_{2} log α + w_{2} log b) + w_{1} log b,

where w_{1} = (s_{i} − s_{i}^{∗})/(n − n^{∗}) and w_{2} = (s_{j} − s_{j}^{∗})/(n − n^{∗}) are rational numbers. Since v_{1}v_{2} ≠ 1, this implies that log α/ log b is rational. Similarly, we see that log β/ log b is rational. But these statements contradict our hypothesis that dim_{ℤ}⟨log α, log β, log b⟩ ≥ 2; therefore, n is bounded, and it follows that n_{i}, n_{j}, s_{i}, and s_{j} are bounded as well.

(iii) The remaining cases.

For the remaining cases, there are only two possibilities:

• E_{1} contains an unknown of the form x_{2i+1} = ε_{i}α^{n_{i}}b^{s_{i}} for some i ≥ 1 and E_{2} contains only unknowns of the form x_{2j+1} = ε_{j}α^{n_{j}}b^{s_{j}} with j ≥ 1 (except for x_{2}).

• E_{1} contains only unknowns of the form x_{2i} = ε_{i}β^{n_{i}}b^{s_{i}} with i ≥ 2 (except for x_{1}) and E_{2} contains an unknown of the form x_{2j} = ε_{j}β^{n_{j}}b^{s_{j}} for some j ≥ 2.

We treat only the first case, as the second case is similar.

We note that the ratio x_{1}/x_{2i+1} = ±α^{n−n_{i}}b^{−s_{i}} assumes only finitely many values. If α and b are multiplicatively independent, it follows that both n − n_{i} and s_{i} are bounded, and we are done. On the other hand, if n−n_{i} is not bounded, it follows that log α/ log b is rational. If j is such that x_{2j+1} ∈ E_{2}, then x_{2}/x_{2j+1} = ±β^{n}α^{−n_{j}}b^{−s_{j}} can take at most finitely many values. Since α and b are multiplicatively dependent, β and b must be multiplicatively independent, and it follows that n can take only finitely many values. But this is impossible if n − n_{i} is unbounded.

The analysis above completes our proof that (10) holds for some i in the case that n_{i} ≤ n − κ for all i = 1, …, t. Combining (9) and (10), we see that the bound

max\{|n − n_{i}|, s_{i}\} ≪ \{ \begin{matrix}1, & if α ∈ ℝ; \\ log n, & if α ∉ ℝ (i.e., α = \overline{β}) \end{matrix}  (12)

holds for some i ∈ {1, …, t} in every case.

We now select i such that (12) holds and rewrite (8) in the form

cα^{n} + dβ^{n} + Ab^{s_{i−1}} + c_{1}α^{n_{i}}b^{s_{i}} + d_{1}β^{n_{i}}b^{s_{i}} + B = 0,  (13)

where c_{1} = −ε_{i}ε_{0}c, d_{1} = −ε_{i}ε_{0}d,

A = − ∑_{j=1}^{i−1} ε_{j}ε_{0}u_{n_{j}}b^{s_{j}−s_{i−1}} and B = − ∑_{j=i+1}^{t} ε_{i}ε_{0}u_{n_{j}}b^{s_{j}}.

Since

b^{s_{i−1}} ≥ |u_{n_{i}}| ≥ |α|^{n_{i}+O(log n_{i})} = |α|^{n+O(log n)},

we see that A = exp(O(log n)). Similarly, since b^{s_{i}} ≥ B, it follows that B = exp(O(log n)).

Assume first that both n − n_{i} and s_{i} are bounded (this is the case, for instance, if 𝕃 is real). In this case, A and B are bounded as well; hence, we can assume that they are fixed. Here, (13) becomes

C_{1}α^{n} + D_{1}β^{n} + Ab^{s_{i−1}} + B = 0,  (14)

where C_{1} = c+c_{1}α^{n_{i}−n} and D_{1} = d+d_{1}β^{n_{i}−n} can also be regarded as fixed numbers. The case A = B = C_{1} = D_{1} = 0 leads to i = t = 1, α^{n−n_{i}} = −cc_{1}^{−1} = ±1 and β^{n−n_{i}} = −dd_{1}^{−1} = ±1; therefore, t = 1, n = n_{1}, and m_{1} = 0, which contradicts our assumption that m_{1} ≥ 1 when t = 1. Consequently, the equation (14) is nontrivial. If any two of the coefficients A, B, C_{1}, D_{1} are zero, then either n or s_{i−1} is bounded, and this leads to at most finitely many possibilities for n. A similar argument based on Theorem 4 can be used if one of the coefficients A, B, C_{1}, D_{1} is zero, or if ABC_{1}D_{1} ≠ 0, to show that there are at most finitely many possibilities for n.

Thus, from now on, we can suppose that either n − n_{i} or s_{i} is unbounded over the set of solutions to (13). In this case, α and β are complex conjugates.

Assume first that B ≠ 0 in equation (13). Suppose also that A ≠ 0. We apply Theorem 3 with N = 5, the linear forms L_{j,μ}(x) = x_{j} for each j = 1, …, 5, and μ ∈ S, except when j = 1 and μ is infinite, in which case we take L_{1,μ}(x) = cx_{1} + dx_{2} + x_{3} + c_{1}x_{4} + d_{1}x_{5} (note that, as 𝕃 is complex quadratic, there is only one infinite place). We evaluate the double product appearing in Theorem 3 for our system of forms and the points x = (α^{n}, β^{n}, Ab^{s_{i−1}}, α^{n_{i}}b^{s_{i}}, β^{n_{i}}b^{s_{i}}). Clearly,

∏_{μ∈S} |L_{j,μ}(x)| = 1  (15)

if j ∈ {2, 4, 5}, since x_{2}, x_{4} and x_{5} are S-units. Moreover,

∏_{μ∈S} |L_{3,μ}(x)| ≤ A = exp(O(log n)).  (16)

Finally, since x_{1} is an S-unit, it follows from the product formula (3) that

∏_{\begin{matrix}μ∈S \\ μ finite \end{matrix}} |L_{1,μ}(x)|_{μ} = \frac{1}{|Nm_{𝕃}(α^{n})|} ≤ \frac{1}{|α|^{n}} ,  (17)

while by equation (13), we have

∏_{μ∈S ; μ is infinite} |L_{1,μ}(x)|_{μ} = B^{2} ≤ exp(O(log n)).  (18)

Multiplying the estimates (15), (16), (17) and (18), we derive that

∏_{j=1}^{N} ∏_{μ∈S} |L_{j,μ}(x)| ≤ \frac{AB^{2}}{α^{n}} ≤ exp (−n log α + O(log n)) .  (19)

Since max{|x_{j}| : j = 1, …, N} = |α|^{n}, the inequality (19) together with Theorem 3 (for example, with ε = 1/2 and n > n_{ε}), imply that there exist finitely many proper subspaces of 𝕃^{N} containing all solutions x. Thus, the relation

C_{2}α^{n} + D_{2}β^{n} + C_{3}α^{n_{i}}b^{s_{i}} + D_{3}β^{n_{i}}b^{s_{i}} + EAb^{s_{i}−1} = 0  (20)

holds for some fixed coefficients C_{2}, D_{2}, C_{3}, D_{3} and E in 𝕃, which are not all equal to zero. If A = 0, then the same argument with N = 4 also yields an identity of the shape (20). Finally, if B = 0, then (13) is the same as (20) with C_{2} = c, D_{2} = d, C_{3} = c_{1}, D_{3} = d_{1}, and E = 1. Clearly, we may assume that C_{2} and D_{2} are conjugate (over 𝕃), that C_{3} and D_{3} are conjugate (over 𝕃), and that E ∈ ℤ (if not, we can conjugate (20) and subtract the result from (20) to obtain a “shorter” nontrivial equation of the same type with the desired properties).

If E = 0, then (20) is a S-unit equation. If it is nondegenerate, we see that α^{n}β^{−n} can take only finitely many values; since α/β is not a root of unity, there are at most finitely many possibilities for n. If the S-unit equation is degenerate, then either C_{2} = D_{2} = 0, in which case n_{i} can take only finitely many values (and since |n − n_{i}| ≪ log n, it follows that n is bounded as well), or C_{2}D_{2} ≠ 0 but C_{3} = D_{3} = 0, in which case n can again take only finitely many values, or C_{2}C_{3}D_{2}D_{3} ≠ 0. In the last case, either α^{n−n_{i}}b^{−s_{i}} and β^{n−n_{i}}b^{−s_{i}} can take only finitely many values, or α^{n}β^{−n_{i}}b^{−s_{i}} and β^{n}α^{−n_{i}}b^{−s_{i}} can take only finitely many values; but these are cases that have already been considered.

Finally, we are left with the possibility that E ≠ 0, in which case we can assume that E = 1. We now rewrite (20) in the form

C_{4}α^{n} + D_{4}β^{n} = −Ab^{s_{i−1}},  (21)

where C_{4} = C_{2} + C_{3}α^{n_{i}−n}b^{s_{i}} and D_{4} = D_{2} + D_{3}β^{n_{i}−n}b^{s_{i}}. Since C_{4} and D_{4} are conjugated in 𝕃, it follows that they are simultaneously zero or nonzero.

Assume first that C_{4} = D_{4} = 0. Then both relations

C_{2} = −C_{3}α^{n−n_{i}}b^{s_{i}}  and D_{2} = −D_{3}β^{n−n_{i}}b^{s_{i}}  (22)

hold. If C_{2} = 0 then C_{3} = 0 (by (22)), D_{2} = 0 (because C_{2} and D_{2} are conjugated), and therefore D_{3} = 0 (by (22)); together with equation (20), these lead to E = 0, which is a contradiction. Thus, C_{2} ≠ 0, and the preceding argument implies that C_{2}C_{3}D_{2}D_{3} ≠ 0. Now, equation (22) together with our hypothesis that dim_{ℚ}⟨log α, log β, log b⟩ ≥ 2 lead to the conclusion that both n − n_{i} and s_{i} are bounded, which is a case already treated.

We now assume that C_{4}D_{4} ≠ 0. Let ℓ = gcd(r^{2}, s), where r and s are the coefficients of the recurrence (1). Set α_{1} = α^{2}/ℓ, β_{1} = β^{2}/ℓ. Applying Lemma A.10 on page 20 in [26], we see that α_{1} and β_{1} are algebraic integers and that the principal ideals they generate in 𝕃 are coprime. Clearly, α_{1} and β_{1} are complex conjugates, and |α_{1}| > 1. Write n = 2m + δ, where δ ∈ {0, 1}. Put (C_{5}, D_{5}) = (C_{4}, D_{4}) if δ = 0 and (C_{5}, D_{5}) = (αC_{4}, βD_{4}) if δ = 1. Dividing both sides of equation (21) by ℓ^{m}, we see that the expression

C_{5}α_{1}^{m} + D_{5}β_{1}^{m}

is a rational number such that every prime factor of its numerator or denominator divides either Abαβ or one of the denominators of C_{2}, D_{2}, C_{3}, or D_{3}. Let P = {p_{1}, …, p_{v}} be the set consisting of all of these primes, and write

C_{5}α^{m} + D_{5}β^{m} = ∏_{i=1}^{v} p_{i}^{r_{i}}.

We now bound the order r_{i} of p_{i}. Let π_{i} be some prime ideal of 𝕃 lying above p_{i}. If π_{i}|α_{1}, then ord_{π_{i}}(α_{1}^{m}) ≥ m ≥ n/2 − 1. On the other hand, it is clear that

max{|ord_{π_{i}}(C_{5})|, |ord_{π_{i}}(D_{5})|} ≪ max{|n − n_{i}|, s_{i}} ≪ log n.

Thus, for large n, we get that

ord_{π_{i}}(C_{5}α_{1}^{m} + D_{5}β_{1}^{m}) = ord_{π_{i}}(D_{5}β_{1}^{m}) = ord_{π_{i}}(D_{5}) ≪ log n,  (23)

since α_{1} and β_{1} are coprime. A similar analysis can be used if π_{i}|β_{1}. Assume now that π_{i} does not divide α_{1}β_{1}. Then

r_{i} = ord_{π_{i}} (C_{5}α_{1}^{m} + D_{5}β_{1}^{m}) = ord_{π_{i}}(C_{5}β_{1}^{m}) + ord_{π_{1}} ((α_{1}/β_{1})^{m} − (−D_{5}/C_{5})) .

Certainly,

ord_{π_{i}}(C_{5}β_{1}^{m}) = ord_{π_{i}}(C_{5}) ≪ log n,

while from Theorem 6, we deduce that

ord_{π_{i}} ((α_{1}/β_{1})^{m} − (−D_{5}/C_{5})) ≪ (log n)^{2}| log |C_{5}|| ≪ (log n)^{3}.

Thus,

ord_{π_{i}}(C_{5}α_{1}^{m} + D_{5}β_{1}^{m}) ≪ (log n)^{3}  (24)

in this case. Comparing inequalities (23) and (24), we see that inequality (24) always holds. Since this is true for all i = 1, …, v, we conclude that

log |C_{5}α_{1}^{m} + D_{5}β_{1}^{m}| ≤ ∑_{i=1}^{v} r_{i} log p_{i} ≪ (log n)^{3}.  (25)

On the other hand, we have

log |C_{5}α_{1}^{m} + D_{5}β_{1}^{m}| = log |C_{5}| + m log |α_{1}| + log |1 + (D_{5}C_{5}^{−1}(β_{1}α_{1}^{−1})^{m}|.

Clearly,

log |C_{5}| ≫ − log n,  (26)

and using Theorem 5, we get that

log |1 + (D_{5}C_{5}^{−1})(β_{1}α_{1}^{−1})^{m}| ≫ −(log n)^{2}| log |C_{5}||.  (27)

Putting together inequalities (25), (26), (27), and using the fact that m ≫ n and |α_{1}| > 1, we obtain that

n ≪ (log n)^{3},

which shows that n can take only finitely many values.

This completes the proof of Theorem 1.

4 Proof of Theorem 2

Before proceeding to the proof of Theorem 2, we gather a few useful facts about the Fibonacci sequence.

We first recall the following special case of the Primitive Divisor Theorem, which is due to Carmichael [5]:

Lemma 7. For all n ≥ 13, there exists a prime factor p of F_{n} such that p does not divide F_{m} for any positive integer m < n. Furthermore, any such prime p satisfies p ≡ ±1 mod n.

Next, we record the following estimate for the function ℓ(n) = ℓ_{10}(F_{n}), which gives the number of digits in the decimal expansion of F_{n}:

Lemma 8. For all n ≥ 1, we have

\frac{(n − 2) log α}{log 10} < ℓ(n) ≤ \frac{(n − 1) log α}{log 10} + 1.

Proof. By induction on k, it is easy to see that α^{k−2} ≤ F_{k} ≤ α^{k−1} holds for all k ≥ 1. Since ℓ(k) is the unique integer for which 10^{ℓ(k)−1} ≤ F_{k} < 10^{ℓ(k)}, the result follows.

We keep the notation used in the proof of Theorem 1. In particular, 𝕃 = ℚ(\sqrt{5} ), O_{𝕃} = ℤ[α], and D = 2 is the degree of 𝕃 over ℚ. Notice that O_{𝕃} is a UFD. We also put ϖ = \sqrt{5} and P = [ϖ]; then [p] = [5] = P^{2}, and f = 1. We need the following elementary lemma:

Lemma 9. If r ≥ 2, we have

ord_{P}(α^{r} − 1) ≤ \frac{2 log(r/4)}{log 5} + 1.

The same inequality holds with α replaced by β.

Proof. The inequality for β follows from the one for α by conjugation. Note that the right hand side of the stated inequality is positive for all r ≥ 2. Since

α = \frac{1 + \sqrt{5}}{2} ≡ 2^{−1} (mod ϖ),

it follows that ord_{P}(α^{r} − 1) = 0 if 4 ∤ r; hence, it suffices to assume that 4 | r in what follows. Since

α^{4} − 1 = \frac{5 + 3\sqrt{5}}{2},

it follows that ord_{P}(α^{4} − 1) = 1. Thus, we may write α^{4} = 1 + ϖu, where u is coprime to ϖ. If s ≥ 1 is an integer and 5 ∤ s, then

α^{4s} − 1 = (α^{4} − 1) ∑_{j=0}^{s−1} α^{4j} = ϖu ∑_{j=0}^{s−1}(1 + ϖu)^{j} ≡ ϖus (mod ϖ),

which shows that ord_{P}(α^{4s} − 1) = 1 as well. One checks similarly that if s ≥ 1 and 5 ∤ s, then ord_{P}(α^{20s} − 1) = 3.

We now claim that, for all t ≥ 0 and s ≥ 1 such that 5 ∤ s, we have

ord_{P}(α^{4s·5^{t}} − 1) = 2t + 1.  (28)

To prove this, we use induction on the parameter t. Since the claim is true for t = 0 or 1, let us suppose that t ≥ 2. Then,

α^{4s·5^{t}} − 1 = (α^{4s·5^{t−1}} − 1) ∑_{j=0}^{4} α^{4sj·5^{t−1}}

= 5(α^{4s·5^{t−1}} − 1) + (α^{4s·5^{t−1}} − 1) ∑_{j=1}^{4}(α^{4sj·5^{t−1}} − 1).

By the induction hypothesis, we have

ord_{P} (5(α^{4s·5^{t−1}} − 1)) = 2 + (2(t − 1) + 1) = 2t + 1,

while

ord_{P} ((α^{4s·5^{t−1}} − 1) ∑_{j=1}^{4}(α^{4sj·5^{t−1}} − 1)) ≥ 2 (2(t − 1) + 1) = 4t − 2 > 2t + 1,

and (28) follows.

Finally, writing r in the form r = 4s · 5^{t}, where t ≥ 0, s ≥ 1, and 5 ∤ s, we have

ord_{P}(α^{r} − 1) = 2t + 1 = \frac{2 log(r/4s)}{log 5} + 1 ≤ \frac{2 log(r/4)}{log 5} + 1,

which finishes the proof.

Lemma 10. If (m, n, k) is an ordered triple of positive integers such that \overline{F_{m}F_{n}} = F_{k}, and (m, n, k) ≠ (1, 4, 7) or (2, 4, 7), then m ≥ 3 and k − n ≥ 4.

Proof. Suppose that n ≥ 13. First, suppose that m = 1 or m = 2. Then 10^{ℓ(n)} + F_{n} = F_{k}; hence, 2F_{n} ≤ F_{k} ≤ 11F_{n}, which (by simple estimates) implies that n + 2 ≤ k ≤ n + 5. Since n ≥ 13, we have that ℓ(n) ≥ 3, and thus,

F_{n} ≡ F_{k} (mod 8).

An analysis of the sequence of Fibonacci numbers modulo 8 shows that this congruence is not possible when k = n + 4 or k = n + 5; therefore, k = n + 2 or k = n + 3. If k = n + 2, then 10^{ℓ(n)} = F_{n+1}, while for k = n + 3, we have 10^{ℓ(n)} = 2F_{n+1}. However, by Lemma 7, there exists a prime p ≥ n dividing F_{n+1}, which is not possible in our cases. Consequently, if m ≤ 2, we must have n ≤ 12. Checking the remaining possibilities, the only solutions found are (1, 4, 7) and (2, 4, 7).

Assuming now that \overline{F_{m}F_{n}} = F_{k}, n ≥ 15, and k ≤ n + 3, we then have

F_{m} · 10^{ℓ(n)} = F_{k} − F_{n} = \{ \begin{matrix}F_{n−1}, & if k = n + 1; \\ F_{n+1}, & if k = n + 2; \\ 2F_{n+1}, & if k = n + 3. \end{matrix}  (29)

Moreover, m < n − 1, for otherwise

F_{k} = F_{m} · 10^{ℓ(n)} + F_{n} > 1000F_{n−1} > F_{n+3},

contradicting our assumption that k ≤ n + 3. Using Lemma 7 again, we see that there exist primes p | F_{n−1} and q | F_{n+1} with gcd(pq, F_{m}) = 1 and min{p, q} ≥ 13, which is not possible in view of (29). Hence, if k ≤ n + 3, we must have n ≤ 14, and thus k ≤ 17. Examining these possibilities reveals no solutions other than the two found in the previous case.

Lemma 11. If r ≥ 1 is even, then

\frac{α^{r} − 1}{β^{r} − 1} = −α^{r},

while if r ≥ 5 is odd, then the numbers (α^{r} − 1)/(β^{r} − 1) and α are multiplicatively independent.

Proof. The first statement is trivial since αβ = −1. For the second statement, we note that if r is odd then

\frac{α^{r} − 1}{β^{r} − 1} = −α^{r} (\frac{α^{r} − 1}{α^{r} + 1}) .

We now observe that if D is the common divisor in O_{𝕃} of α^{r}−1 and α^{r}+1, then D | 2. Since 2 is inert in O_{𝕃}, it follows that D ∈ {1, 2}. The above arguments show that if (α^{r} −1)/(β^{r} −1) and α are multiplicatively dependent, then so are (α^{r} − 1)/(α^{r} + 1) and α. Using the fact that O_{𝕃} is a UFD and the computation of D, it follows that α^{r} − 1 is either a unit, or it is an associate of 2. Hence, we get an equation of the form

α^{r} − 1 = ±2^{λ}α^{t}

with integers λ ∈ {0, 1} and t. Since r > 3, it follows that α^{r} − 1 > α^{3} − 1 > 2; hence, the sign in this equation is positive, and t ≥ 1. Clearly, t < r. Thus, α^{r} − 1 = 2^{λ}α^{t}. By conjugation, we also have β^{r} − 1 = 2^{λ}β^{t}. Subtracting these two equations and dividing the result by α − β, we obtain that F_{r} = 2^{λ}F_{t}. If r ≥ 13, this equation is impossible in view of Lemma 7. The fact that F_{r} = 2^{λ}F_{t} is also impossible for 5 ≤ r ≤ 13 can be checked by hand, and the result follows.

We are now ready to embark on the proof of Theorem 2. For this, let (m, n, k) be a fixed triple of nonnegative integers for which \overline{F_{m}F_{n}} = F_{k} holds. We note that n > 0, since for n = 0 we have 10F_{m} = F_{k}, which has no positive integer solutions (m, k) (by Lemma 7, for example). Put r = k − n, and assume that k > 10^{6}. By Lemma 10, we can further suppose that m ≥ 3 and r ≥ 4. Since β = −1/α, we have

F_{m} · 10^{ℓ(n)} = F_{k} − F_{n} = ϖ^{−1}(α^{k} − β^{k} − α^{n} + β^{n})
= ϖ^{−1}(α^{n}(α^{r} − 1) − β^{n}(β^{r} − 1))
= ϖ^{−1}α^{n}(β^{r} − 1) ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n}) .

Consequently,

ord_{P}(F_{m}) + 2ℓ(n) = −1 + ord_{P}(β^{r} − 1) + ord_{P} ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n}) .  (30)

Assume first that r is odd. We apply Theorem 6 with the choices α_{1} = (α^{r} − 1)/(β^{r} − 1), α_{2} = −α^{−2}, b_{1} = 1, and b_{2} = n. The condition that α_{1} and α_{2} are multiplicatively independent is satisfied by Lemma 11 because r ≥ 5. Furthermore, note that

h(α_{1}) ≤ \frac{1}{2} (log |(α^{r} − 1)(β^{r} − 1)| + log |α_{1}|) ≤ \frac{1}{2} log α^{2r} = r log α,

and h(α_{2}) = log α. Since r ≥ 5, we can choose A_{1} = α^{r} and A_{2} = ϖ; hence,

b′ = \frac{1}{log 5} + \frac{n}{2r log α} ≤ \frac{1}{2 log α} + \frac{n}{10 log α} ≤ \frac{3n}{4 log α}.

Finally, as α ≡ β (mod ϖ), and ord_{P}(α^{r} − 1) = ord_{P}(β^{r} − 1) = 0 (by Lemma 9), it follows that P divides α_{1} − 1. Moreover, noting that −α^{−2} ≡ 1 (mod ϖ), it follows that P also divides α_{2} − 1. Thus, we can take g = 1. By Theorem 6, we obtain the bound

ord_{P} ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n})
≤ \frac{480r log α}{(log 5)^{3}} (max \{log n + log (\frac{3 log 5}{4 log α}) + 0.4, 10\})^{2}
≤ 56r (max {log n + 2, 10})^{2} .

Next, consider the case that r is even; then

\frac{α^{r} − 1}{β^{r} − 1} − (α^{−2})^{n} = −α^{r} − (−α^{2})^{n} = (−1)^{n+1}α^{−2n}(α^{k+n} ± 1),

and the last expression divides α^{2k+2n} − 1 in O_{𝕃}; hence, by Lemma 9, we obtain that

ord_{P} ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n}) ≤ \frac{2 log((k + n)/2)}{log 5} + 1.

Substituting the estimates above into (30), and applying Lemmas 8 and 9, we derive that

2\frac{(n − 2) log α}{log 10} < ℓ(n) ≤ \frac{2 log(r/4)}{log 5} + 56r (max \{log n + 2, 10\})^{2} ,  (31)

if r is odd, and

2\frac{(n − 2) log α}{log 10} < ℓ(n) ≤ \frac{2 log(r/4)}{log 5} + \frac{2 log((k + n)/2)}{log 5} + 1,  (32)

if r is even.

From the equality \overline{F_{m}F_{n}} = F_{k}, we also see that

α^{m} · 10^{ℓ(n)} − α^{k} = β^{m} · 10^{ℓ(n)} − α^{n} + β^{n} − β^{k},  (33)

and, since 10^{ℓ(n)} < 10F_{n} and m ≥ 3, we have

\begin{aligned}|α^{m−k} · 10^{ℓ(n)} − 1| & = α^{−k}|β^{m} · 10^{ℓ(n)} − α^{n} + β^{n} − β^{k}| \\ & ≤ α^{−k}(10|β|^{3}F_{n} + α^{n} + 2) < 4α^{−r}. \end{aligned}  (34)

Since m ≥ 3, both sides of (33) are negative, and since r ≥ 4, we have 4α^{−r} < \frac{3}{5}; thus,

\frac{2}{5} < α^{m−k} · 10^{ℓ(n)} < 1.

It follows that

|α^{m−k} · 10^{ℓ(n)} − 1| > \frac{2}{5}|(k − m) log α − ℓ(n) log 10|.  (35)

We now apply Theorem 5 with the choices Λ = (k − m) log α − ℓ(n) log 10, α_{1} = 10, α_{2} = α, b_{1} = ℓ(n), and b_{2} = k − m. Here, h(α_{1}) = log 10 and h(α_{2}) = \frac{1}{2} log α; hence, we can choose A_{1} = 10, and A_{2} = α^{2}, and

b′ = \frac{ℓ(n)}{4 log α} + \frac{k − m}{20} < b′′ = \frac{ℓ(n)}{4 log α} + \frac{k}{20}.

Using Theorem 5, we get that

|(k − m) log α − ℓ(n) log 10| ≥ exp (−864 (max{log b′′ + 0.14, 10.5})^{2}) .

Combining the above estimates, we derive the bound

r < \frac{log 10}{log α} + \frac{864}{log α} (max\{log b′′ + 0.14, 10.5\})^{2} .  (36)

Now, if k > 2n, then, by Lemma 8, we have

b′′ = \frac{ℓ(n)}{4 log α} + \frac{k}{20} ≤ \frac{n − 1}{4 log 10} + \frac{1}{4 log α} + \frac{k}{20} < \frac{(k/2) − 1}{4 log 10} + \frac{1}{4 log α} + \frac{k}{20},

and r = k − n > k/2; hence, the inequality (36) is not possible for k > 500000. On the other hand, if k ≤ 2n, then

b′′ = \frac{ℓ(n)}{4 log α} + \frac{k}{20} ≤ \frac{n − 1}{4 log 10} + \frac{1}{4 log α} + \frac{n}{10}.

When r is even, estimate (32) gives

\frac{(n − 2) log α}{log 10} < \frac{log(n/4)}{log 5} + \frac{log(3n/2)}{log 5} + \frac{1}{2},

which implies that n < 20; hence, k < 40. When r is odd, by combining the inequalities (31), and (36), we obtain a contradiction unless n ≤ 1.1 × 10^{11} and k ≤ 2n ≤ 2.2 × 10^{11}.

Although the preceding argument shows that there are only finitely many solutions (m, n, k) to the equation \overline{F_{m}F_{n}} = F_{k}, it would be computationally infeasible to search for solutions over the entire range k ≤ 2.2 × 10^{11}. In order to reduce the range further, we use a standard technique involving the continued fraction expansion of (log 10)/(log α).

Suppose that n ≤ 1.1 × 10^{11} and r ≥ 56. By (34) and (35), we have

|\frac{log 10}{log α} − \frac{(k − m)}{ℓ(n)}| < \frac{10}{α^{r}ℓ(n)} ≤ \frac{1}{2ℓ(n)^{2}} .

Here, the last inequality is equivalent to 20ℓ(n) ≤ α^{r}, which holds (by Lemma 8) for this choice of parameters. By well known properties of continued fractions, it follows that the fraction (k − m)/ℓ(n) is a convergent of (log 10)/(log α). Writing (k − m)/ℓ(n) = p_{j}/q_{j} for some j ≥ 0, where p_{j}/q_{j} denotes the jth convergent to (log 10)/(log α), and using Lemma 8 again to bound ℓ(n) for n in our range, we see that q_{j} ≤ ℓ(n) ≤ 2.3 × 10^{10}, which implies that j ≤ 23. Noting that

10α^{−r} > |ℓ(n) log 10 − (k − m) log α| ≥ min_{1≤j≤23} |q_{j} log 10 − p_{j} log α| > 1.6 × 10^{−11},

we conclude that r ≤ 57. Substituting this estimate into (31), we derive the more tractable upper bound n ≤ 2.1 × 10^{6}.

At this point, we turn to the computer. Note that if n ≥ 74, one has ℓ(n) ≥ 15; therefore, if \overline{F_{m}F_{n}} = F_{k}, it follows that F_{n} ≡ F_{k} (mod 10^{15}). However, a computer search quickly reveals that there is no solution to this congruence with 74 ≤ n ≤ 2.1 × 10^{6} and k ≤ n+57. Thus, it remains only to search for solutions (m, n, k) with n ≤ 73 and k ≤ n+57, and one obtains only solutions with k = 7, 8 or 10; that is F_{k} ∈ {13, 21, 55}.

This completes the proof of Theorem 2.

5 Acknowledgements

The authors wish to thank the referee for his detailed and insightful comments on the original manuscript, which led to improvements in the quality, accuracy, and completeness of the paper. This work was done during a visit by the second author to the University of Missouri, Columbia; the hospitality and support of this institution are gratefully acknowledged. During the preparation of this paper, W. B. was supported in part by NSF grant DMS-0070628, and F. L. was supported in part by grants SEP-CONACYT 37259-E and 37260-E.

References

[1] W. Banks, A. Conflitti and I. E. Shparlinski, Character sums over integers with restricted g-ary digits, Illinois J. Math. 46 (2002), 819–836.

[2] W. Banks, D. Hart and M. Sakata, Almost all palindromes are composite, Math. Res. Lett. 11 (2004), 853–868.

[3] W. Banks and I. E. Shparlinski, On the number of sparse RSA exponents, J. Number Theory 95 (2002), 340–350.

[4] Y. Bugeaud and M. Laurent, Minoration effective de la distance p-adique entre puissances de nombres algébriques, J. Number Theory 61 (1996), 311–342.

[5] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n}1β^{n}, Ann. of Math. (2) 15 (1913/14), 30–70.

[6] P. Erdős, C. Mauduit and A. Sárközy, On arithmetic properties of integers with missing digits, I, J. Number Theory 70 (1998), 99–120.

[7] P. Erdős, C. Mauduit and A. Sárközy, On arithmetic properties of integers with missing digits, II, Discrete Math. 200 (1999), 149–164.

[8] J.-H. Evertse, H. P. Schlickewei and W. M. Schmidt, Linear equations with variables which lie in a multiplicative group, Ann. of Math. (2) 155 (2002), 807–836.

[9] M. Filaseta and S. V. Konyagin, Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arith. 74 (1996), 191–205.

[10] E. Fouvry and C. Mauduit, Methódes des crible et fonctions sommes des chiffres, Acta Arith. 77 (1996), 339–351.

[11] E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, Math. Ann. 305 (1996), 571–599.

[12] J. B. Friedlander and I. E. Shparlinski, On the distribution of Diffie–Hellman triples with sparse exponents, SIAM J. Discrete Math. 14 (2001), 162–169.

[13] A. O. Gel’fond, Sur les nombres qui ont des propriétés additives et multiplicatives données, Acta Arith. 13 (1968), 259–265.

[14] S. V. Konyagin, Arithmetic properties of integers with missing digits: distribution in residue classes, Period. Math. Hungar. 42 (2001), 145–162.

[15] S. V. Konyagin, C. Mauduit and A. Sárkőzy, On the number of prime factors of integers characterized by digit properties, Period. Math. Hungar. 40 (2000), 37–52.

[16] F. Luca, Distinct digits in base b expansions of linear recurrence sequences, Quaest. Math. 23 (2000), 389–404.

[17] F. Luca, Arithmetic properties of positive integers with fixed digit sum, to appear in Rev. Mat. Iberoamericana.

[18] C. Mauduit and A. Sárközy, On the arithmetic structure of sets characterized by sum of digits properties, J. Number Theory 61 (1996), 25–38.

[19] C. Mauduit and A. Sárközy, On the arithmetic structure of the integers whose sum of digits is fixed, Acta Arith. 81 (1997), 145–173.

[20] M. Laurent, M. Mignotte and Y. Nesterenko, Formes linéaires en deux logarithmes et déterminants d’interpolation, J. Number Theory 55 (1995), 285–321.

[21] H. P. Schlickewei, S-unit equations over number fields, Invent. Math. 102 (1990), 95– 107.

[22] W. M. Schmidt, Diophantine Approximations, Springer Verlag, LNM 785 (1980).

[23] W. M. Schmidt, Diophantine Approximations and Diophantine Equations, Springer Verlag, LNM 1467 (1991).

[24] H. G. Senge and E. G. Straus, PV-numbers and sets of multiplicity, in Proceedings of the Washington State Conference in Number Theory (Washington State Univ., Pullman, Wash., 1971), 55–67, Dept. Math. Washington State Univ., Pullman, Washington, 1971.

[25] H. G. Senge and E. G. Straus, PV-numbers and sets of multiplicity, in “Collection of articles dedicated to the memory of Alfréd Rényi, II”, Period. Math. Hungar. 3 (1973), 93–100.

[26] T. N. Shorey and R. Tijdeman, Exponential diophantine equations, Cambridge Univ. Press, 1986.

[27] I. E. Shparlinski, Prime divisors of sparse integers, Period. Math. Hungar. 46 (2003), 215–222.

[28] C. L. Stewart, On the representation of an integer in two different bases, J. Reine Angew. Math. 319 (1980), 63–72.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 11J86 . Keywords: binary recurrent sequences, Fibonacci numbers, digits.

Received August 30 2004; revised version received January 13 2005. Published in Journal of Integer Sequences, January 14 2005. Small revisions, January 17 2005.

Return to Journal of Integer Sequences home page.