Powers of Two as Sums of Two Lucas Numbers

Jhon J. Bravo Mathematics Department

University of Cauca Street 5 No. 4-70 Popayán, Cauca

Colombia

jbravo@unicauca.edu.co

Florian Luca School of Mathematics

University of the Witwatersrand

P. O. Box Wits 2050

South Africa

and

Mathematical Institute

UNAM Juriquilla Santiago de Querétaro 76230

Querétaro de Arteaga

Mexico

fluca@matmor.unam.mx

Abstract

Let (L_{n})_{n≥0} be the Lucas sequence given by L_{0} = 2, L_{1} = 1 and L_{n+2} = L_{n+1} + L_{n} for n ≥ 0. In this paper, we are interested in finding all powers of two which are sums of two Lucas numbers, i.e., we study the Diophantine equation L_{n} + L_{m} = 2^{a} in nonnegative integers n, m, and a. The proof of our main theorem uses lower bounds for linear forms in logarithms, properties of continued fractions, and a version of the Baker-Davenport reduction method in diophantine approximation. This paper continues our previous work where we obtained a similar result for the Fibonacci numbers.

1 Introduction

Let (F_{n})_{n≥0} be the Fibonacci sequence given by F_{0} = 0, F_{1} = 1 and F_{n+2} = F_{n+1} + F_{n} for all n ≥ 0. The Fibonacci numbers are famous for possessing wonderful and amazing properties. They are accompanied by the sequence of Lucas numbers, which is as important as the Fibonacci sequence. The Lucas sequence (L_{n})_{n≥0} follows the same recursive pattern as the Fibonacci numbers, but with initial conditions L_{0} = 2 and L_{1} = 1.

The study of properties of the terms of such sequences, or more generally, linear recurrence sequences, has a very long history and has generated a huge literature. For the beauty and rich applications of these numbers and their relatives, one can see Koshy’s book [9].

For example, a remarkable property of the Fibonacci sequence is that 1, 2 and 8 are the only Fibonacci numbers which are powers of 2. One proof of this fact follows from Carmichael’s primitive divisor theorem [6], which states that for n greater than 12, the nth Fibonacci number F_{n} has at least one prime factor that is not a factor of any previous Fibonacci number (see the paper of Bilu, Hanrot, and Voutier [2] for the most general version of the above statement). Similarly, it is well known that 1, 2 and 4 are the only powers of 2 that appear in the Lucas sequence.

The problem of finding all perfect powers in the Fibonacci sequence and the Lucas sequence was a famous open problem finally solved in 2006 in a paper in Annals of Mathematics by Bugeaud, Mignotte, and Siksek [3]. In their work, they applied a combination of Baker’s method, the modular approach and some classical techniques to show that the only perfect powers in the Fibonacci sequence are 0, 1, 8 and 144, and the only perfect powers in the Lucas sequence are 1 and 4. A detailed account of this problem can be found in [3, Section 10].

In our recent paper [5], we found all powers of 2 which are the sums of at most two Fibonacci numbers. Specifically, we proved the following.

Theorem 1. The only solutions of the Diophantine equation F_{n} + F_{m} = 2^{a} in positive integers n, m and a with n ≥ m are given by

2F_{1} = 2, 2F_{2} = 2, 2F_{3} = 4, 2F_{6} = 16,

and

F_{2} + F_{1} = 2, F_{4} + F_{1} = 4, F_{4} + F_{2} = 4, F_{5} + F_{4} = 8, F_{7} + F_{4} = 16.

In this paper, we prove an analogue of Theorem 1 when the sequence of Fibonacci numbers is replaced by the sequence of the Lucas numbers, i.e., we extend our previous work [5] and determine all the solutions of the Diophantine equation

L_{n} + L_{m} = 2^{a}  (1)

in nonnegative integers n ≥ m and a.

Similar problems have recently been investigated. For example, repdigits which are sums of at most three Fibonacci numbers were found by Luca [12]; Fibonacci numbers which are sums of two repdigits were obtained by Díaz and Luca [7], while factorials which are sums of at most three Fibonacci numbers were found by Luca and Siksek [11].

We prove the following result.

Theorem 2. All solutions of the Diophantine equation (1) in nonnegative integers n ≥ m and a, are

2L_{0} = 4, 2L_{1} = 2, 2L_{3} = 8, L_{2} + L_{1} = 4, L_{4} + L_{1} = 8 and L_{7} + L_{2} = 32.

Let us give a brief overview of our strategy for proving Theorem 2. First, we rewrite equation (1) in suitable ways in order to obtain two different linear forms in logarithms which are both nonzero and small. Next, we use a lower bound on such nonzero linear forms in two logarithms due to Laurent, Mignotte, and Nesterenko as well as a general lower bound due to Matveev to find an absolute upper bound for n; hence, an absolute upper bound for m and a, which we then reduce using standard facts concerning continued fractions.

In this paper, we follow the approach and the presentation described in [5].

2 Auxiliary results

Before proceeding further, we recall that the Binet formula

L_{n} = α^{n} + β^{n} holds for all n ≥ 0,

where

α := \frac{1 + \sqrt{5}}{2} and β := \frac{1 − \sqrt{5}}{2}

are the roots of the characteristic equation x^{2} − x − 1 = 0 of (L_{n})_{n≥0}. This will be an important ingredient in what follows. In particular, the inequality

α^{n−1} ≤ L_{n} ≤ 2α^{n}  (2)

holds for all n ≥ 0.

In order to prove Theorem 2, we need a result of Laurent, Mignotte, and Nesterenko [10] about linear forms in two logarithms. But first, some notation.

Let η be an algebraic number of degree d with minimal polynomial

a_{0}x^{d} + a_{1}x^{d−1} + ⋯ + a_{d} = a_{0} ∏_{i=1}^{d}(X − η^{(i)}),

where the a_{i}’s are relatively prime integers with a_{0} > 0 and the η^{(i)}’s are conjugates of η. Then

h(η) = \frac{1}{d} (log a_{0} + ∑_{i=1}^{d} log (max\{|η^{(i)}|, 1\}))

is called the logarithmic height of η. In particular, if η = p/q is a rational number with gcd(p, q) = 1 and q > 0, then h(η) = log max{|p|, q}.

The following properties of the logarithmic height, which will be used in the next section without special reference, are also known:

• h(η ± γ) ≤ h(η) + h(γ) + log 2.

• h(ηγ^{±1}) ≤ h(η) + h(γ).

• h(η^{s}) = |s|h(η).

With the above notation, Laurent, Mignotte, and Nesterenko [10, Corollary 1] proved the following theorem.

Theorem 3. Let γ_{1}, γ_{2} be two non-zero algebraic numbers, and let log γ_{1} and log γ_{2} be any determinations of their logarithms. Put D = [ℚ(γ_{1}, γ_{2}) : ℚ]/[ℝ(γ_{1}, γ_{2}) : ℝ], and

Γ := b_{2} log γ_{2} − b_{1} log γ_{1},

where b_{1} and b_{2} are positive integers. Further, let A_{1}, A_{2} be real numbers > 1 such that

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

Then, assuming that γ_{1} and γ_{2} are multiplicatively independent, we have

log |Γ| > −30.9 · D^{4} (max \{log b′, \frac{21}{D}, \frac{1}{2}\})^{2} log A_{1} · log A_{2},

where

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

We shall also need the following general lower bound for linear forms in logarithms due to Matveev [13] (see also the paper of Bugeaud, Mignotte, and Siksek [3, Theorem 9.4]).

Theorem 4 (Matveev’s theorem). Assume that γ_{1}, …, γ_{t} are positive real algebraic numbers in a real algebraic number field 𝕂 of degree D, b_{1}, …, b_{t} are rational integers, and

Λ := γ_{1}^{b_{1}} ⋯ γ_{t}^{b_{t}} − 1,

is not zero. Then

|Λ| > exp (−1.4 · 30^{t+3} · t^{4.5} · D^{2}(1 + log D)(1 + log B)A_{1} ⋯ A_{t}) ,

where

B ≥ max{|b_{1}|, …, |b_{t}|},

and

A_{i} ≥ max{Dh(γ_{i}), | log γ_{i}|, 0.16}, for all i = 1, …, t.

In 1998, Dujella and Pethő in [8, Lemma 5 (a)] gave a version of the reduction method based on the Baker-Davenport lemma [1]. To conclude this section of auxiliary results, we present the following lemma from [4], which is an immediate variation of the result due to Dujella and Pethő from [8], and will be one of the key tools used in this paper to reduce the upper bounds on the variables of the equation (1).

Lemma 5. Let M be a positive integer, let p/q be a convergent of the continued fraction of the irrational γ such that q > 6M, and let A, B, μ be some real numbers with A > 0 and B > 1. Let ϵ := ||μq|| − M||γq||, where || · || denotes the distance from the nearest integer. If ϵ > 0, then there is no solution to the inequality

0 < uγ − v + μ < AB^{−w},

in positive integers u, v and w with

u ≤ M and w ≥ \frac{log(Aq/ϵ)}{log B}.

3 The Proof of Theorem 2

Assume throughout that equation (1) holds. First of all, observe that if n = m, then the original equation (1) becomes L_{n} = 2^{a−1}. But the only solutions of this latter equation are (n, a) ∈ {(0, 2), (1, 1), (3, 3)} and this fact has already been mentioned in the Introduction. So, from now on, we assume that n > m.

If n ≤ 200, then a brute force search with Mathematica in the range 0 ≤ m < n ≤ 200 gives the solutions (n, m, a) ∈ {(2, 1, 2), (4, 1, 3), (7, 2, 5)}. This took a few seconds. Thus, for the rest of the paper we assume that n > 200.

Let us now get a relation between n and a. Combining (1) with the right inequality of (2), one gets that

2^{a} ≤ 2α^{n} + 2α^{m} < 2^{n+1} + 2^{m+1} = 2^{n+1}(1 + 2^{m−n}) ≤ 2^{n+1}(1 + 2^{−1}) < 2^{n+2},

which leads to a ≤ n + 1. This estimate is essential for our purpose.

On the other hand, we rewrite equation (1) as

α^{n} − 2^{a} = −β^{n} − L_{m}.

We now take absolute values in the above relation obtaining

|α^{n} − 2^{a}| ≤ |β|^{n} + L_{m} < \frac{1}{2} + 2α^{m}.

Dividing both sides of the above expression by α^{n} and taking into account that n > m, we get

|1 − 2^{a} · α^{−n}| < \frac{3}{α^{n−m}} .  (3)

In order to apply Theorem 3, we take γ_{1} := α, γ_{2} := 2, b_{1} := n and b_{2} := a. So,

Γ := b_{2} log γ_{2} − b_{1} log γ_{1},

and therefore estimation (3) can be rewritten as

|1 − e^{Γ}| < \frac{3}{α^{n−m}} .  (4)

The algebraic number field containing γ_{1}, γ_{2} is ℚ(\sqrt{5}), so we can take D := 2. By using (1) and the Binet formula for the Lucas sequence, we have

α^{n} = L_{n} − β^{n} < L_{n} + 1 ≤ L_{n} + L_{m} = 2^{a}.

Consequently, 1 < 2^{a} α^{−n} and so Γ > 0. This, together with (4), gives

0 < Γ < \frac{3}{α^{n−m}} ,  (5)

where we have also used the fact that x ≤ e^{x} − 1 for all x ∈ ℝ. Hence,

log Γ < log 3 − (n − m) log α.  (6)

Note further that h(γ_{1}) = (log α)/2 = 0.2406 ⋯ and h(γ_{2}) = log 2 = 0.6931 ⋯; thus, we can choose log A_{1} := 0.5 and log A_{2} := 0.7. Finally, by recalling that a ≤ n + 1, we get

b′ = \frac{n}{1.4} + a < 1.71429 n + 1 < 2n.

Since α and 2 are multiplicatively independent, we have, by Theorem 3, that

log Γ ≥ − 30.9 · 2^{4} · (max {log(2n), 21/2, 1/2})^{2} · 0.5 · 0.7
> − 174 · (max {log(2n), 21/2, 1/2})^{2} .  (7)

We now combine (6) and (7) to obtain

(n − m) log α < 180 · (max {log(2n), 21/2})^{2} .  (8)

Let us now get a second linear form in logarithms. To this end, we now rewrite (1) as follows:

α^{n}(1 + α^{m−n}) − 2^{a} = −β^{n} − β^{m}.

Taking absolute values in the above relation and using the fact that β = (1 − \sqrt{5})/2, we get

|α^{n}(1 + α^{m−n}) − 2^{a}| = |β|^{n} + |β|^{m} < 2

for all n > 200 and m ≥ 0. Dividing both sides of the above inequality by the first term of the left-hand side, we obtain

|1 − 2^{a} · α^{−n} · (1 + α^{m−n})^{−1}| < \frac{2}{α^{n}} .  (9)

We are now ready to apply Matveev’s result Theorem 4. To do this, we take the parameters t := 3 and

γ_{1} := 2, γ_{2} := α, γ_{3} := 1 + α^{m−n}.

We take b_{1} := a, b_{2} := −n and b_{3} := −1. As before, 𝕂 := ℚ(\sqrt{5}) contains γ_{1}, γ_{2}, γ_{3} and has D := [𝕂 : ℚ] = 2. To see why the left-hand side of (9) is not zero, note that otherwise, we would get the relation

2^{a} = α^{n} + α^{m}.  (10)

Conjugating the above relation in ℚ(\sqrt{5}), we get

2^{a} = β^{n} + β^{m}.  (11)

Combining (10) and (11), we obtain

α^{n} < α^{n} + α^{m} = |β^{n} + β^{m}| ≤ |β|^{n} + |β|^{m} < 2,

which is impossible for n > 200. Hence, indeed the left-hand side of inequality (9) is nonzero.

In this application of Matveev’s theorem we take A_{1} := 1.4 and A_{2} := 0.5. Since a ≤ n+1 it follows that we can take B := n + 1. Let us now estimate h(γ_{3}). We begin by observing that

γ_{3} = 1 + α^{m−n} < 2 and γ_{3}^{−1} = \frac{1}{1 + α^{m−n}} < 1,

so that | log γ_{3}| < 1. Next, notice that

h(γ_{3}) ≤ |m − n| (\frac{log α}{2}) + log 2 = log 2 + (n − m) (\frac{log α}{2}) .

Hence, we can take

A_{3} := 2 + (n − m) log α > max{2h(γ_{3}), | log γ_{3}|, 0.16}.

Now Matveev’s theorem implies that a lower bound on the left-hand side of (9) is

exp (−C · (1 + log(n + 1)) · 1.4 · 0.5 · (2 + (n − m) log α)

where C := 1.4 · 30^{6} · 3^{4.5} · 2^{2}(1 + log 2) < 9.7 × 10^{11}. So, inequality (9) yields

n log α − log 2 < 1.36 × 10^{12} log n · (2 + (n − m) log α),  (12)

where we used the inequality 1 + log(n + 1) < 2 log n, which holds because n > 200.

Using now (8) in the right-most term of the above inequality (12) and performing the respective calculations, we arrive at

n < 6 × 10^{14} log n · (max {log(2n), 21/2})^{2} .  (13)

If max {log(2n), 21/2} = 21/2, it then follows from (13) that n < 8 × 10^{16} log n giving n < 3.5 × 10^{18}. If on the other hand we have that max {log(2n), 21/2} = log(2n), then, from (13), we get n < 6 × 10^{14} log n log^{2}(2n) and so n < 5.9 × 10^{19}. In any case, we have that n < 5.9 × 10^{19} always holds. We summarize what we have proved so far in the following lemma.

Lemma 6. If (n, m, a) is a solution in positive integers of equation (1) with n > m and n > 200, then inequalities

a ≤ n + 1 < 6 × 10^{19}

hold.

4 Reducing the bound on n

After finding an upper bound on n the next step is to reduce it. To do this, we first use some properties of continued fractions to obtain a suitable upper bound on n − m, and secondly we use Lemma 5 to conclude that n must be relatively small. Let us see.

Turning back to inequality (5), we obtain

0 < a log 2 − n log α < \frac{3}{α^{n−m}} .

Dividing across by log α, we get

0 < aγ − n < \frac{7}{α^{n−m}} , where γ := \frac{log 2}{log α}.  (14)

Let [a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, …] = [1, 2, 3, 1, 2, …] be the continued fraction expansion of γ, and let denote p_{k}/q_{k} its kth convergent. Recall also that a < 6 × 10^{19} by Lemma 6.

A quick inspection using Mathematica reveals that

54475119544877440894 = q_{44} < 6 × 10^{19} < q_{45} = 67219577652603468483.

Furthermore, a_{M} := max{a_{i} | i = 0, 1, …, 45} = a_{17} = 134. So, from the known properties of continued fractions, we obtain that

|aγ − n| > \frac{1}{(a_{M} + 2)a}.  (15)

Comparing estimates (14) and (15), we get right away that

α^{n−m} < 7 · 136 · a < 6 × 10^{22},

leading to n − m ≤ 110. Let us now work a little bit on (9) in order to find an improved upper bound on n. Put

z := a log 2 − n log α − log φ(n − m),  (16)

where φ is the function given by the formula φ(t) := 1 + α^{−t}. Therefore, (9) implies that

|1 − e^{z}| < \frac{2}{α^{n}} .  (17)

Note that z ≠ 0; thus, we distinguish the following cases. If z > 0, then, from (17), we obtain

0 < z ≤ e^{z} − 1 < \frac{2}{α^{n}} .

Replacing z in the above inequality by its formula (16) and dividing both sides of the resulting inequality by log α, we get

0 < a (\frac{log 2}{log α}) − n − \frac{log φ(n − m)}{log α} < 5 · α^{−n}.  (18)

We now put

γ := \frac{log 2}{log α}, μ := −\frac{log φ(n − m)}{log α}, A := 5 and B := α.

Clearly γ is an irrational number. We also put M := 6×10^{19}, which is an upper bound on a by Lemma 6. We therefore apply Lemma 5 to inequality (18) for all choices n−m ∈ {1, …, 110} except when n − m = 1, 3 and get that

n < \frac{log(Aq/ϵ)}{log B},

where q > 6M is a denominator of a convergent of the continued fraction of γ such that ϵ = ||μq|| − M||γq|| > 0. Indeed, with the help of Mathematica we find that if (n, m, a) is a possible solution of the equation (1) with z > 0 and n − m ≠ 1, 3, then n ≤ 130. This is false because our assumption that n > 200.

Suppose now that z < 0. First, note that 2/α^{n} < 1/2 since n > 200. Then, from (17), we have that |1 − e^{z}| < 1/2 and therefore e^{|z|} < 2. Since z < 0, we have

0 < |z| ≤ e^{|z|} − 1 = e^{|z|}|e^{z} − 1| < \frac{4}{α^{n}} .

Then, by the same arguments used for proving (18), we obtain

0 < n (\frac{log α}{log 2}) − a + \frac{log φ(n − m)}{log 2} < 6 · α^{−n}.  (19)

Here, we also take M := 6 × 10^{19}, which is an upper bound on n by Lemma 6, and we apply Lemma 5 to inequality (19) for each n − m ∈ {1, …, 110} except for n − m = 1, 3. In this case, with the help of Mathematica, we find that if (n, m, a) is a possible solution of the equation (1) with z < 0 and n − m ≠ 1, 3, then n ≤ 120, which is false.

Finally, we deal with the cases when n − m = 1 and 3. We cannot study these cases as before because when applying Lemma 5 to the expressions (18) or (19) (according to whether z is positive or negative, respectively), the corresponding parameter μ appearing in Lemma 5 is either

−\frac{log φ(t)}{log α} = \begin{cases}−1, & if t = 1; \\ 1 − \frac{log 2}{log α}, & if t = 3. \end{cases} or \frac{log φ(t)}{log 2} = \begin{cases}\frac{log α}{log 2}, & if t = 1; \\ 1 − \frac{log α}{log 2}, & if t = 3. \end{cases}

But, in any case, one can see that the corresponding value of ϵ from Lemma 5 is always negative and therefore the reduction method is not useful for reducing the bound on n in these instances. For this reason we need to treat these cases differently.

All we want to do here is solve the equations

L_{m+1} + L_{m} = 2^{a} and L_{m+3} + L_{m} = 2^{a}  (20)

in positive integers m and a with m + 1 > 200 and m + 3 > 200, respectively. But, by definition L_{m+1} + L_{m} = L_{m+2}. Moreover, L_{m+3} + L_{m} = 2L_{m+2}, which is easily checked. We see from the above discussion that equations (20) are transformed into the simpler equations

L_{m+2} = 2^{a} and L_{m+2} = 2^{a−1}  (21)

to be resolved in positive integers m and a with m > 199 and m > 197, respectively. But, we quickly see that the above equations (21) have no solutions for m > 1 as mentioned earlier. This completes the analysis of the cases when n − m = 1, 3 and therefore the proof of Theorem 2.

5 Acknowledgments

We thank the referee for suggestions which improved the quality of this paper. J. J. B. was partially supported by University of Cauca and F. L. was supported in part by Project PAPIIT IN104512, UNAM, Mexico.

References

[1] A. Baker and H. Davenport, The equations 3x^{2} − 2 = y^{2} and 8x^{2} − 7 = z^{2}, Quart. J. Math. Oxford Ser. 20 (1969), 129–137.

[2] Yu. Bilu, G. Hanrot, and P. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers (with an appendix by M. Mignotte), J. Reine Angew. Math. 539 (2001), 75– 122.

[3] Y. Bugeaud, M. Mignotte, and S. Siksek, Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers, Ann. of Math. 163 (2006), 969–1018.

[4] J. J. Bravo and F. Luca, On a conjecture about repdigits in k−generalized Fibonacci sequences, Publ. Math. Debrecen 82 (2013), 623–639.

[5] J. J. Bravo and F. Luca, On the Diophantine equation F_{n} + F_{m} = 2^{a}, preprint, 2014.

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

[7] S. Díaz Alvarado and F. Luca, Fibonacci numbers which are sums of two repdigits, Proceedings of the XIVth International Conference on Fibonacci numbers and their applications, 2011, pp. 97–111.

[8] A. Dujella and A. Pethő, A generalization of a theorem of Baker and Davenport, Quart. J. Math. Oxford Ser. 49 (1998), no. 195, 291–306.

[9] T. Koshy, Fibonacci and Lucas numbers with Applications, Wiley-Interscience Publications, 2001.

[10] M. Laurent, M. Mignotte, and Y. Nesterenko, Formes linéaires en deux logarithmes et déterminants d’interpolation, (French) (Linear forms in two logarithms and interpolation determinants), J. Number Theory 55 (1995), 285–321.

[11] F. Luca and S. Siksek, Factorials expressible as sums of two and three Fibonacci numbers, Proc. Edinb. Math. Soc. 53 (2010), 747–763.

[12] F. Luca, Repdigits as sums of three Fibonacci numbers, Math. Commun. 17 (2012), 1–11.

[13] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers, II, Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), 125–180. Translation in Izv. Math. 64 (2000), 1217–1269.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11J86. Keywords: Fibonacci number, Lucas number, linear forms in logarithms, continued fraction, reduction method.

(Concerned with sequences \underline{A000032} and \underline{A000045}.)

Received March 17 2014; revised versions received July 22 2014; July 30 2014. Published in Journal of Integer Sequences, July 30 2014.

Return to Journal of Integer Sequences home page.