# On the problem of Pillai with *k*-generalized Fibonacci numbers and powers of 3

Mahadi Ddamulira, Florian Luca

► To cite this version:

Mahadi Ddamulira, Florian Luca. On the problem of Pillai with *k*-generalized Fibonacci numbers and powers of 3. International Journal of Number Theory, 2020, pp.1-24. 10.1142/S1793042120500876. hal-02139945v2

HAL Id: hal-02139945

https://hal.science/hal-02139945v2

Submitted on 9 Apr 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the problem of Pillai with *k*-generalized Fibonacci numbers and powers of 3

Mahadi Ddamulira*

Institute of Analysis and Number Theory

Graz University of Technology

Kopernikusgasse 24/II, A- 8010 Graz, Austria

mddamulira@tugraz.at; mahadi@aima.edu.gh

Florian Luca

School of Mathematics, University of the Witwatersrand

Private Bag X3, WITS 2050, Johannesburg, South Africa

Research Group in Algebraic Structures and Applications

King Abdulaziz University, Jeddah, Saudi Arabia

Centro de Ciencias Matemáticas, UNAM

Morelia, Michoacán, Mexico

Florian.Luca@wits.ac.za

Received 22 May 2019

Revised 3 March 2020

Accepted 3 March 2020

Published 9 April 2020

For an integer $k \ge 2$, let $\{F_n^{(k)}\}_{n \ge 2-k}$ be the *k*-generalized Fibonacci sequence which starts with $0, \dots, 0, 1$ (a total of $k$ terms) and for which each term afterwards is the sum of the $k$ preceding terms. In this paper, we find all integers $c$ with at least two representations as a difference between a *k*-generalized Fibonacci number and a power of 3. This paper continues the previous work of the first author for the Fibonacci numbers, and for the Tribonacci numbers.

**Keywords:** Pillai's problem; generalized Fibonacci numbers; linear forms in logarithms; Baker's method.

Mathematics Subject Classification 2020: 11B39, 11D45, 11D61, 11J86

<footnote>*Corresponding author.</footnote>

<footnote>This is an Open Access article published by World Scientific Publishing Company. It is distributed under the terms of the Creative Commons Attribution 4.0 (CC BY) License which permits use, distribution and reproduction in any medium, provided the original work is properly cited.</footnote>
# 1. Introduction

The problem of Pillai states that for each fixed integer $c \ge 1$, the Diophantine equation

$$a^x - b^y = c, \quad \min\{x, y\} \ge 2, \qquad (1.1)$$

has only a finite number of positive solutions $\{a, b, x, y\}$. This problem is still open; however, the case $c = 1$ is the conjecture of Catalan and was proved by Mihăilescu [22]. In 1936 (see [23, 24]), in the special case $(a, b) = (3, 2)$ which is a continuation of the work of Herschfeld [19, 20] in 1935, Pillai conjectured that the only integers $c$ admitting at least two representations of the form $2^x - 3^y$ are given by

$$2^3 - 3^2 = 2^1 - 3^1 = -1, \quad 2^5 - 3^3 = 2^3 - 3^1 = 5, \quad 2^8 - 3^5 = 2^4 - 3^1 = 13. \quad (1.2)$$

This was confirmed by Stroeker and Tijdeman [25] in 1982. The general problem of Pillai is difficult to solve and this has motivated the consideration of special cases of this problem. In the past years, several special cases of the problem of Pillai have been studied. For example, see [6, 8–12, 17, 18].

Let $k \ge 2$ be an integer. We consider a generalization of Fibonacci sequence called the $k$-generalized Fibonacci sequence $\{F_n^{(k)}\}_{n \ge 2-k}$ defined as

$$F_n^{(k)} = F_{n-1}^{(k)} + F_{n-2}^{(k)} + \cdots + F_{n-k}^{(k)}, \qquad (1.3)$$

with the initial conditions

$$F_{-(k-2)}^{(k)} = F_{-(k-3)}^{(k)} = \cdots = F_0^{(k)} = 0 \quad \text{and} \quad F_1^{(k)} = 1.$$

We call $F_n^{(k)}$ the $n$th $k$-generalized Fibonacci number. Note that when $k = 2$, it coincides with the Fibonacci numbers and when $k = 3$ it is the Tribonacci number. The first $k + 1$ nonzero terms in $F_n^{(k)}$ are powers of 2, namely

$$F_1^{(k)} = 1, \quad F_2^{(k)} = 1, \quad F_3^{(k)} = 2, \quad F_4^{(k)} = 4, \quad \dots, \quad F_{k+1}^{(k)} = 2^{k-1}.$$

Furthermore, the next term is $F_{k+2}^{(k)} = 2^k - 1$. Thus, we have that

$$F_n^{(k)} = 2^{n-2} \quad \text{holds for all } 2 \le n \le k+1. \qquad (1.4)$$

We also observe that the recursion (1.3) implies the three-term recursion

$$F_n^{(k)} = 2F_{n-1}^{(k)} - F_{n-k-1}^{(k)} \quad \text{for all } n \ge 3,$$

which can be used to prove by induction on $m$ that $F_n^{(k)} < 2^{n-2}$ for all $n \ge k + 2$ (see also [5, Lemma 2]).

The generalized Fibonacci analogue of the problem of Pillai under the same conditions as in (1.1) concerns studying for fixed $(k, \ell)$ all values of the integer $c$ such that the equation

$$F_n^{(k)} - F_m^{(\ell)} = c \qquad (1.5)$$
has at least two solutions $(n, m)$. We are not aware of a general treatment of equation (1.5) (namely, considering $k$ and $\ell$ parameters), although the particular case when $\{k, \ell\} = \{2, 3\}$ was treated by Chim, Pink and Ziegler in [8].

Ddamulira, Gómez and Luca [13] studied the Diophantine equation

$$F_n^{(k)} - 2^m = c, \qquad (1.6)$$

where $k$ is also a parameter, which is a variation of Eq. (1.5). They determined all integers $c$ such that Eq. (1.6) has at least two solutions $(n, m)$. These $c$ together with their multiple representations as in (1.6) turned out to be grouped into four parametric families.

In this paper, we study a related problem and we find all integers $c$ admitting at least two representations of the form $F_n^{(k)} - 3^m$ for some positive integers $k, n$, and $m$. This can be interpreted as solving the equation

$$F_n^{(k)} - 3^m = F_{n_1}^{(k)} - 3^{m_1} \quad (=c) \qquad (1.7)$$

with $(n, m) \neq (n_1, m_1)$. The cases $k = 2$ and $k = 3$ have been solved completely by the first author in [10, 11], respectively. So, we focus on the case $k \ge 4$.

Our main result is the following.

**Theorem 1.1.** For fixed integer $k \ge 4$, the Diophantine equation (1.7) with $n > n_1 \ge 2$ and $m > m_1 \ge 1$ has solutions with:

(i) $c \in \{-1, 5, 13\}$ and $2 \le n \le k+1$, which arise from the classical Pillai problem for $(a, b) = (2, 3)$, namely:

$$F_5^{(k)} - 3^2 = F_3^{(k)} - 3^1 = -1, \quad k \ge 4,$$

$$F_7^{(k)} - 3^3 = F_5^{(k)} - 3^1 = 5, \quad k \ge 6,$$

$$F_{10}^{(k)} - 3^5 = F_6^{(k)} - 3^1 = 13, \quad k \ge 9;$$

(ii) $c \in \{-25, -7, 5\}$ and $n \ge k+2$ and $k \in \{4, 5, 6\}$. Furthermore, all the representations of $c$ in this case are given by

$$F_8^{(4)} - 3^4 = F_3^{(4)} - 3^3 = -25,$$

$$F_{10}^{(5)} - 3^5 = F_3^{(5)} - 3^2 = -7,$$

$$F_{10}^{(6)} - 3^5 = F_6^{(6)} - 3^1 = 5,$$

for $k = 4, 5$, and $6$, respectively.

## 2. Preliminary Results

In this section, we recall some general results from algebraic number theory and Diophantine approximations and properties of the $k$-generalized Fibonacci sequence.
## 2.1. Notations and terminology from algebraic number theory

We begin by recalling some basic notions from algebraic number theory.

Let $\eta$ be an algebraic number of degree $d$ with minimal primitive polynomial over the integers

$$a_0x^d + a_1x^{d-1} + \dots + a_d = a_0 \prod_{i=1}^{d} (x - \eta^{(i)}),$$

where the leading coefficient $a_0$ is positive and the $\eta^{(i)}$'s are the conjugates of $\eta$. Then the logarithmic height of $\eta$ is given by

$$h(\eta) := \frac{1}{d} \left( \log a_0 + \sum_{i=1}^{d} \log(\max\{|\eta^{(i)}|, 1\}) \right).$$

In particular, if $\eta = p/q$ is a rational number with $\gcd(p, q) = 1$ and $q > 0$, then $h(\eta) = \log \max\{|p|, q\}$. The following are some of the properties of the logarithmic height function $h(\cdot)$, which will be used in the next sections of this paper without reference:

$$h(\eta \pm \gamma) \le h(\eta) + h(\gamma) + \log 2,$$

$$h(\eta\gamma^{\pm 1}) \le h(\eta) + h(\gamma),$$

$$h(\eta^s) = |s|h(\eta) \quad (s \in \mathbb{Z}).$$

## 2.2. k-generalized Fibonacci numbers

It is known that the characteristic polynomial of the k-generalized Fibonacci numbers $F^{(k)} := (F_m^{(k)})_{m \ge 2-k}$, namely

$$\Psi_k(x) := x^k - x^{k-1} - \dots - x - 1,$$

is irreducible over $\mathbb{Q}[x]$ and has just one root outside the unit circle. Let $\alpha := \alpha(k)$ denote that single root, which is located between $2(1 - 2^{-k})$ and $2$ (see [14]). This is called the dominant root of $F^{(k)}$. To simplify notation, in our application we shall omit the dependence on $k$ of $\alpha$. We shall use $\alpha^{(1)}, \dots, \alpha^{(k)}$ for all roots of $\Psi_k(x)$ with the convention that $\alpha^{(1)} := \alpha$.

We now consider for an integer $k \ge 2$, the function

$$f_k(z) = \frac{z-1}{2+(k+1)(z-2)} \quad \text{for } z \in \mathbb{C}. \qquad (2.1)$$

With this notation, Dresden and Du presented in [14] the following “Binet-like” formula for the terms of $F^{(k)}$:

$$F_m^{(k)} = \sum_{i=1}^{k} f_k(\alpha^{(i)}) \alpha^{(i)^{m-1}}. \qquad (2.2)$$
It was proved in [14] that the contribution of the roots which are inside the unit circle to the formula (2.2) is very small, namely that the approximation

$$|F_m^{(k)} - f_k(\alpha)\alpha^{m-1}| < \frac{1}{2} \quad \text{holds for all } m \ge 2-k. \qquad (2.3)$$

It was proved by Bravo and Luca in [5] that

$$\alpha^{m-2} \le F_m^{(k)} \le \alpha^{m-1} \quad \text{holds for all } m \ge 1 \text{ and } k \ge 2. \qquad (2.4)$$

Before we conclude this section, we present some useful lemma that will be used in the next sections on this paper. The following lemma was proved by Bravo and Luca in [5].

**Lemma 2.1 (Bravo, Luca).** Let $k \ge 2$, $\alpha$ be the dominant root of $\{F_m^{(k)}\}_{m \ge 2-k}$, and consider the function $f_k(z)$ defined in (2.1).

(i) The inequalities

$$\frac{1}{2} < f_k(\alpha) < \frac{3}{4} \quad \text{and} \quad |f_k(\alpha^{(i)})| < 1, \quad 2 \le i \le k$$

hold. In particular, the number $f_k(\alpha)$ is not an algebraic integer.

(ii) The logarithmic height of $f_k(\alpha)$ satisfies $h(f_k(\alpha)) < 3 \log k$.

## 2.3. Linear forms in logarithms and continued fractions

In order to prove our main result (Theorem 1.1), we need to use several times a Baker-type lower bound for a nonzero linear form in logarithms of algebraic numbers. There are many such in the literature like that of Baker and Wüstholz from [2]. We recall the result of Bugeaud, Mignotte and Siksek [7, Theorem 9.4, p. 989], which is a modified version of the result of Matveev [21]. This result is one of our main tools in this paper.

**Theorem 2.2 (Matveev according to Bugeaud, Mignotte, Siksek).** Let $\gamma_1, \dots, \gamma_t$ be positive real algebraic numbers in a real algebraic number field $\mathbb{K}$ of degree $D$, $b_1, \dots, b_t$ be nonzero integers, and assume that

$$\Lambda := \gamma_1^{b_1} \cdots \gamma_t^{b_t} - 1$$

is nonzero. Then

$$\log |\Lambda| > -1.4 \times 30^{t+3} \times t^{4.5} \times D^2(1 + \log D)(1 + \log B)A_1 \cdots A_t,$$

where

$$B \ge \max\{|b_1|, \dots, |b_t|\},$$

and

$$A_i \ge \max\{Dh(\gamma_i), |\log \gamma_i|, 0.16\}, \quad \text{for all } i = 1, \dots, t.$$

During the course of our calculations, we get some upper bounds on our variables which are too large, thus we need to reduce them. To do so, we use some results
from the theory of continued fractions. Specifically, for a nonhomogeneous linear form in two integer variables, we use a slight variation of a result due to Dujella and Pethő (see [15, Lemma 5a]), which itself is a generalization of a result of Baker and Davenport [1].

For a real number $X$, we write $||X|| := \min\{|X - n| : n \in \mathbb{Z}\}$ for the distance from $X$ to the nearest integer.

**Lemma 2.3 (Dujella, Pethő).** Let $M$ be a positive integer, $p/q$ be a convergent of the continued fraction of the irrational number $\tau$ such that $q > 6M$, and $A, B, \mu$ be some real numbers with $A > 0$ and $B > 1$. Furthermore, let $\varepsilon := ||\mu q|| - M||\tau q||$. If $\varepsilon > 0$, then there is no solution to the inequality

$$0 < |u\tau - v + \mu| < AB^{-w},$$

in positive integers $u, v$, and $w$ with

$$u \le M \quad \text{and} \quad w \ge \frac{\log(Aq/\varepsilon)}{\log B}.$$

The above lemma cannot be applied when $\mu = 0$ (since then $\varepsilon < 0$). In this case, we use the following criterion of Legendre, a well-known result from the theory of Diophantine approximation.

**Lemma 2.4 (Legendre).** Let $\tau$ be real number and $x, y$ integers such that

$$\left|\tau - \frac{x}{y}\right| < \frac{1}{2y^2}.$$

Then $x/y = p_k/q_k$ is a convergent of $\tau$. Furthermore,

$$\left|\tau - \frac{x}{y}\right| \ge \frac{1}{(a_{k+1} + 2)y^2}.$$

Finally, the following lemma is also useful. It is [16, Lemma 7].

**Lemma 2.5 (Gúzman Sánchez, Luca).** If $m \ge 1$, $T > (4m^2)^m$, and $T > x/(\log x)^m$, then

$$x < 2^m T (\log T)^m.$$

### 3. The Connection with the Classical Pillai Problem

Assume that $(n, m) \ne (n_1, m_1)$ are such that

$$F_n^{(k)} - 3^m = F_{n_1}^{(k)} - 3^{m_1}.$$

If $m = m_1$, then $F_n^{(k)} = F_{n_1}^{(k)}$ and since $\min\{n, n_1\} \ge 2$, we get that $n = n_1$. Thus, $(n, m) = (n_1, m_1)$, contradicting our assumption. Hence, $m \ne m_1$, and we may assume without loss of generality that $m > m_1 \ge 1$. Since

$$F_n^{(k)} - F_{n_1}^{(k)} = 3^m - 3^{m_1}, \qquad (3.1)$$
and the right-hand side of (3.1) is positive, we get that the left-hand side of (3.1) is also positive and so $n > n_1$. Furthermore, since $F_1^{(k)} = F_2^{(k)} = 1$, we may assume that $n > n_1 \ge 2$.

We analyze the possible situations.

**Case 3.1.** Assume that $2 \le n_1 < n \le k+1$. Then, by (1.4), we have

$$F_{n_1}^{(k)} = 2^{n_1-2} \quad \text{and} \quad F_n^{(k)} = 2^{n-2}$$

so, by substituting them in (3.1), we get

$$2^{n-2} - 3^m = 2^{n_1-2} - 3^{m_1}.$$

By comparing with the classical solutions in (1.2), and by using the fact that $F_n^{(k)}$ is a power of 2 if and only if $n \le k+1$ (see [4]), we get the solutions

$$F_5^{(k)} - 3^2 = F_3^{(k)} - 3^1 = -1, \quad k \ge 4;$$

$$F_7^{(k)} - 3^3 = F_5^{(k)} - 3^2 = 5, \quad k \ge 6;$$

$$F_{10}^{(k)} - 3^5 = F_6^{(k)} - 3^1 = 13, \quad k \ge 9.$$

**Case 3.2.** Assume $n \ge k+2$. The following lemma is useful.

**Lemma 3.1.** For $n \ge k+2$, the conditions

$$F_n^{(k)} - 3^m = F_{n_1}^{(k)} - 3^{m_1} \quad \text{and} \quad 2^{n-2} - 3^m = 2^{n_1-2} - 3^{m_1}$$

cannot simultaneously hold.

**Proof.** If they do, then

$$2^{n-2} - F_n^{(k)} = 2^{n_1-2} - F_{n_1}^{(k)}.$$

The sequence $\{2^{n-2} - F_n^{(k)}\}_{n \ge 2}$ is 0 at $n=2, 3, \dots, k+1$ and is 1 at $n=k+2$. We show that from here on it is increasing. That is

$$2^{n-1} - F_{n+1}^{(k)} > 2^{n-2} - F_n^{(k)} \quad \text{holds for } n \ge k+2.$$

This is equivalent to

$$2^{n-2} > F_{n+1}^{(k)} - F_n^{(k)} = F_{n-1}^{(k)} + \dots + F_{n+1-k}^{(k)},$$

and this last inequality holds true because in the right-hand side we have $F_i \le 2^{i-2}$ for $i = n+1-k, n+2-k, \dots, n-1$ and then

$$\sum_{i=n-k+1}^{n-1} F_i \le \sum_{i=n-k+1}^{n-1} 2^{i-2} < 1 + 2 + \dots + 2^{n-3} < 2^{n-2}.$$

□
4. Bounding *n* in Terms of *m* and *k*

By the results of the previous section, we assume that $n \ge k+2$. Thus, $2^{n-2} - 3^m \ne 2^{n_1-2} - 3^{m_1}$. Since $n > n_1 \ge 2$, we have that $F_{n_1}^{(k)} \le F_{n-1}^{(k)}$ and therefore

$$F_n^{(k)} = F_{n-1}^{(k)} + \dots + F_{n-k}^{(k)} \ge F_{n-1}^{(k)} + \dots + F_{n-k-1}^{(k)} \ge F_{n_1}^{(k)} + \dots + F_{n-k-1}^{(k)}$$

So, from the above, (2.4) and (3.1), we have

$$\alpha^{n-4} \le F_{n-2}^{(k)} \le F_n^{(k)} - F_{n_1}^{(k)} = 3^m - 3^{m_1} < 3^m, \quad \text{and} \quad (4.1)$$

$$\alpha^{n-1} \ge F_n^{(k)} > F_n^{(k)} - F_{n_1}^{(k)} = 3^m - 3^{m_1} \ge 3^{m-1},$$

leading to

$$1 + \left( \frac{\log 3}{\log \alpha} \right) (m-1) < n < \left( \frac{\log 3}{\log \alpha} \right) m + 4. \quad (4.2)$$

We note that the above inequality (4.2) in particular implies that $m < n < 1.6m + 4$. We assume for technical reasons that $n > 600$. By (2.3) and (3.1), we get

$$\begin{aligned} |f_k(\alpha)\alpha^{n-1} - 3^m| \\ &= |(f_k(\alpha)\alpha^{n-1} - F_n^{(k)}) + (F_{n_1}^{(k)} - 3^{m_1})| \\ &= |(f_k(\alpha)\alpha^{n-1} - F_n^{(k)}) + (F_{n_1}^{(k)} - f_k(\alpha)\alpha^{n_1-1}) + (f_k(\alpha)\alpha^{n_1-1} - 3^{m_1})| \\ &< \frac{1}{2} + \frac{1}{2} + \alpha^{n_1-1} + 3^{m_1} \\ &< \alpha^{n_1} + 3^{m_1} \\ &< 2 \max\{\alpha^{n_1}, 3^{m_1}\}. \end{aligned}$$

In the above, we have also used the fact that $|f_k(\alpha)| < 1$ (see Lemma 2.1). Dividing through by $3^m$, we get

$$\begin{aligned} |f_k(\alpha)\alpha^{n-1}3^{-m} - 1| &< 2 \max \left\{ \frac{\alpha^{n_1}}{3^m}, 3^{m_1-m} \right\} \\ &< \max\{\alpha^{n_1-n+6}, 3^{m_1-m+1}\}, \end{aligned} \quad (4.3)$$

where for the right-most inequality in (4.3) we used (4.1) and the fact that $\alpha^2 > 2$.

For the left-hand side of (4.3), we apply Theorem 2.2 with the data

$$t := 3, \quad \gamma_1 := f_k(\alpha), \quad \gamma_2 := \alpha, \quad \gamma_3 := 3, \quad b_1 := 1, \quad b_2 := n-1, \quad b_3 := -m.$$

We begin by noticing that the three numbers $\gamma_1, \gamma_2, \gamma_3$ are positive real numbers and belong to the field $K := \mathbb{Q}(\alpha)$, so we can take $D := [K : \mathbb{Q}] = k$. Put

$$\Lambda := f_k(\alpha)\alpha^{n-1}3^{-m} - 1.$$

To see why $\Lambda \ne 0$, note that otherwise, we would then have that $f_k(\alpha) = 3^m \alpha^{-(n-1)}$ and so $f_k(\alpha)$ would be an algebraic integer, which contradicts Lemma 2.1(i).
Since $h(\gamma_2) = (\log \alpha)/k < (\log 2)/k$ and $h(\gamma_3) = \log 3$, it follows that we can take $A_2 := \log 2$ and $A_3 := k \log 3$. Further, in view of Lemma 2.1(ii), we have that $h(\gamma_1) < 3 \log k$, so we can take $A_1 := 3k \log k$. Finally, since $\max\{1, n-1, m\} = n-1$, we take $B := n$.

Then, the left-hand side of (4.3) is bounded below, by Theorem 2.2, as

$$ \log |\Lambda| > -1.4 \times 30^6 \times 3^{4.5} \times k^4(1 + \log k)(1 + \log n)(3 \log k)(\log 2)(\log 3). $$

Comparing with (4.3), we get

$$ \min\{(n - n_1 - 6) \log \alpha, (m - m_1 - 1) \log 3\} < 6.54 \times 10^{11} k^4 \log^2 k(1 + \log n), $$

which gives

$$ \min\{(n - n_1) \log \alpha, (m - m_1) \log 3\} < 6.60 \times 10^{11} k^4 \log^2 k(1 + \log n). $$

Now the argument is split into two cases.

**Case 4.1.** $\min\{(n - n_1) \log \alpha, (m - m_1) \log 2\} = (n - n_1) \log \alpha$.

In this case, we rewrite (3.1) as

$$ \begin{aligned} & |f_k(\alpha)\alpha^{n-1} - f_k(\alpha)\alpha^{n_1-1} - 3^m| \\ & = |(f_k(\alpha)\alpha^{n-1} - F_n^{(k)}) + (F_{n_1}^{(k)} - f_k(\alpha)\alpha^{n_1-1}) - 3^{m_1}| \\ & < \frac{1}{2} + \frac{1}{2} + 3^{m_1} \le 3^{m_1+1}. \end{aligned} $$

Dividing through by $3^m$ gives

$$ |f_k(\alpha)(\alpha^{n-n_1}-1)\alpha^{n_1-1}3^{-m}-1| < 3^{m_1-m+1}. \quad (4.4) $$

Now we put

$$ \Lambda_1 := f_k(\alpha)(\alpha^{n-n_1}-1)\alpha^{n_1-1}3^{-m}-1. $$

We apply again Theorem 2.2 with the following data:

$$ t := 3, \quad \gamma_1 := f_k(\alpha)(\alpha^{n-n_1}-1), \quad \gamma_2 := \alpha, \quad \gamma_3 := 3, $$

$$ b_1 := 1, \quad b_2 := n_1 - 1, \quad b_3 := -m. $$

As before, we begin by noticing that the three numbers $\gamma_1, \gamma_2, \gamma_3$ belong to the field $\mathbb{K} := \mathbb{Q}(\alpha)$, so we can take $D := [\mathbb{K} : \mathbb{Q}] = k$. To see why $\Lambda_1 \neq 0$, note that otherwise, we would get the relation $f_k(\alpha)(\alpha^{n-n_1}-1) = 3^m\alpha^{1-n_1}$. Conjugating this last equation with any automorphism $\sigma$ of the Galois group of $\Psi_k(x)$ over $\mathbb{Q}$ such that $\sigma(\alpha) = \alpha^{(i)}$ for some $i \ge 2$, and then taking absolute values, we arrive at the equality $|f_k(\alpha^{(i)})((\alpha^{(i)})^{n-n_1}-1)| = |3^m(\alpha^{(i)})^{1-n_1}|$. But this cannot hold because, $|f_k(\alpha^{(i)})||(\alpha^{(i)})^{n-n_1}-1| < 2$ since $|f_k(\alpha^{(i)})| < 1$ by Lemma 2.1(i), and $|(\alpha^{(i)})^{n-n_1}| < 1$, since $n > n_1$, while $|3^m(\alpha^{(i)})^{1-n_1}| \ge 3$.

Since

$$ h(\gamma_1) \le h(f_k(\alpha)) + h(\alpha^{n-n_1}-1) < 3 \log k + (n - n_1) \frac{\log \alpha}{k} + \log 2, $$
it follows that

$$kh(\gamma_1) < 6k \log k + (n - n_1) \log \alpha < 6k \log k + 6.60 \times 10^{11} k^4 \log^2 k (1 + \log n).$$

So, we can take $A_1 := 6.80 \times 10^{11} k^4 \log^2 k (1 + \log n)$. Further, as before, we take $A_2 := \log 2$ and $A_3 := k \log 3$. Finally, by recalling that $m < n$, we can take $B := n$.

We then get that

$$\log |\Lambda_1| > -1.4 \times 30^6 \times 3^{4.5} \times k^3(1 + \log k)(1 + \log n)(6.80 \times 10^{11} k^4 \log^2 k \\ \times (1 + \log n))(\log 2)(\log 3),$$

which yields

$$\log |\Lambda_1| > -7.41 \times 10^{22} k^7 \log^3 k (1 + \log n)^2.$$

Comparing this with (4.4), we get that

$$(m - m_1) \log 3 < 7.50 \times 10^{22} k^7 \log^3 k (1 + \log n)^2.$$

**Case 4.2.** $\min\{(n - n_1) \log \alpha, (m - m_1) \log 3\} = (m - m_1) \log 3$.

In this case, we write (3.1) as

$$\begin{aligned} & |f_k(\alpha)\alpha^{n-1} - 3^m + 3^{m_1}| \\ &= |(f_k(\alpha)\alpha^{n-1} - F_n^{(k)}) + (F_{n_1}^{(k)} - f_k(\alpha)\alpha^{n_1-1}) + f_k(\alpha)\alpha^{n_1-1}| \\ &< \frac{1}{2} + \frac{1}{2} + \alpha^{n_1-1} < \alpha^{n_1}, \end{aligned}$$

so that

$$|f_k(\alpha)(3^{m-m_1}-1)^{-1}\alpha^{n-1}3^{-m_1}-1| < \frac{\alpha^{n_1}}{3^m-3^{m_1}} \le \frac{2\alpha^{n_1}}{3^m} < \alpha^{n_1-n+6}. \quad (4.5)$$

The above inequality (4.5) suggests once again studying a lower bound for the absolute value of

$$\Lambda_2 := f_k(\alpha)(3^{m-m_1}-1)^{-1}\alpha^{n-1}3^{-m_1}-1.$$

We again apply Matveev's theorem with the following data:

$$t := 3, \quad \gamma_1 := f_k(\alpha)(3^{m-m_1}-1)^{-1}, \quad \gamma_2 := \alpha, \quad \gamma_3 := 3,$$

$$b_1 := 1, \quad b_2 := n-1, \quad b_3 := -m_1.$$

We can again take $B := n$ and $\mathbb{K} := \mathbb{Q}(\alpha)$, so that $D := k$. We also note that, if $\Lambda_2 = 0$, then $f_k(\alpha) = \alpha^{-(n-n_1)}3^{m_1}(3^{m-m_1}-1)$ implying that $f_k(\alpha)$ is an algebraic integer, which is not the case. Thus, $\Lambda_2 \neq 0$.

Now, we note that

$$h(\gamma_1) \le h(f_k(\alpha)) + h(3^{m-m_1}-1) < 3 \log k + (m - m_1 + k) \frac{\log 3}{k}.$$

Thus, $kh(\gamma_1) < 4k \log k + (m - m_1) \log 3 < 6.80 \times 10^{11} k^4 \log^2 k (1 + \log n)$, and so we can take $A_1 := 6.80 \times 10^{11} k^4 \log^2 k (1 + \log n)$. As before, we take $A_2 := \log 2$
and $A_3 := k \log 3$. It then follows from Matveev's theorem, after some calculations, that

$$ \log |\Lambda_2| > -7.41 \times 10^{22} k^7 \log^3 k (1 + \log n)^2. $$

From this and (4.5), we obtain that

$$ (n - n_1) \log \alpha < 7.50 \times 10^{22} k^7 \log^3 k (1 + \log n)^2. $$

Thus, in both Cases 4.1 and 4.2, we have

$$ \min\{(n - n_1) \log \alpha, (m - m_1) \log 2\} < 6.6 \times 10^{11} k^4 \log^2 k (1 + \log n), \quad (4.6) $$

$$ \max\{(n - n_1) \log \alpha, (m - m_1) \log 2\} < 7.5 \times 10^{22} k^7 \log^3 k (1 + \log n)^2. $$

We now finally rewrite Eq. (3.1) as

$$ \begin{aligned} & |f_k(\alpha)\alpha^{n-1} - f_k(\alpha)\alpha^{n_1-1} - 3^m + 3^{m_1}| \\ & = |(f_k(\alpha)\alpha^{n-1} - F_n^{(k)}) + (F_{n_1}^{(k)} - f_k(\alpha)\alpha^{n_1-1})| < 1. \end{aligned} $$

We divide through both sides by $3^m - 3^{m_1}$ getting

$$ \left| \frac{f_k(\alpha)(\alpha^{n-n_1}-1)}{3^{m-m_1}-1} \alpha^{n_1-1} 3^{-m_1} - 1 \right| < \frac{1}{3^m - 3^{m_1}} \le \frac{2}{3^m} < 3^{5-0.8n}, \quad (4.7) $$

since $n < 1.6m + 4$. To find a lower-bound on the left-hand side of (4.7), we again apply Theorem 2.2 with the data

$$ \begin{aligned} t &:= 3, & \gamma_1 &:= \frac{f_k(\alpha)(\alpha^{n-n_1}-1)}{3^{m-m_1}-1}, & \gamma_2 &:= \alpha, & \gamma_3 &:= 3, \\ b_1 &:= 1, & b_2 &:= n_1 - 1, & b_3 &:= -m_1. \end{aligned} $$

We also take $B := n$ and we take $K := \mathbb{Q}(\alpha)$ with $D := k$. From the properties of the logarithmic height function, we have that

$$ \begin{aligned} kh(\gamma_1) &\le k(h(f_k(\alpha)) + h(\alpha^{n-n_1}-1) + h(3^{m-m_1}-1)) \\ &< 3k \log k + (n-n_1) \log \alpha + k(m-m_1) \log 3 + 2k \log 2 \\ &< 8.3 \times 10^{22} k^8 \log^3 k (1+\log n)^2, \end{aligned} $$

where in the above chain of inequalities we used the bounds (4.6). So we can take $A_1 := 8.3 \times 10^{22} k^8 \log^3 k (1 + \log n)^2$, and certainly as before we take $A_2 := \log 2$ and $A_3 := k \log 3$. We need to show that if we put

$$ \Lambda_3 := \frac{f_k(\alpha)(\alpha^{n-n_1}-1)}{3^{m-m_1}-1} \alpha^{n_1-1} 3^{-m_1} - 1, $$

then $\Lambda_3 \neq 0$. To see why $\Lambda_3 \neq 0$, note that otherwise, we would get the relation

$$ f_k(\alpha)(\alpha^{n-n_1}-1) = 3^{m_1}\alpha^{1-n_1}(3^{m-m_1}-1). $$
Again, as for the case of $\Lambda_1$, conjugating the above relation with an automorphism $\sigma$ of the Galois group of $\Psi_k(x)$ over $\mathbb{Q}$ such that $\sigma(\alpha) = \alpha^{(i)}$ for some $i \ge 2$, and then taking absolute values, we get that

$$|f_k(\alpha^{(i)})((\alpha^{(i)})^{n-n_1}-1)| = |3^{m_1}(\alpha^{(i)})^{1-n_1}(3^{m-m_1}-1)|.$$

This cannot hold true because in the left-hand side we have

$$f_k(\alpha^{(i)})||(\alpha^{(i)})^{n-n_1}-1| < 2,$$

while in the right-hand side we have $|3^{m_1}||(\alpha^{(i)})^{1-n_1}||3^{m-m_1}-1| \ge 4$. Thus, $\Lambda_3 \ne 0$. Then Theorem 2.2 gives

$$\log|\Lambda_3| > -1.4 \times 30^6 \times 3^{4.5} k^{11} (1 + \log k)(1 + \log n) \\ \times (8.3 \times 10^{22} \log^3 k(1 + \log n)^2)(\log 2)(\log 3),$$

which together with (4.7) gives

$$(0.8n - 5) \log 3 < 9.05 \times 10^{33} k^{11} \log^4 k (1 + \log n)^3.$$

The above inequality leads to

$$n < 6.2 \times 10^{34} k^{11} \log^4 k \log^3 n,$$

which can be equivalently written as

$$\frac{n}{(\log n)^3} < 6.2 \times 10^{34} k^{11} \log^4 k. \qquad (4.8)$$

We apply Lemma 2.5 with the data $m = 3$, $x = n$, $T = 6.2 \times 10^{34} k^{11} \log^4 k$. Inequality (4.8) yields

$$n < 8 \times (6.2 \times 10^{34} k^{11} \log^4 k) \log(6.2 \times 10^{34} k^{11} \log^4 k)^3 \\ < 4 \times 10^{42} k^{11} (\log k)^7.$$

We then record what we have proved so far as a lemma.

**Lemma 4.1.** If $(n, m, n_1, m_1, k)$ is a solution in positive integers to Eq. (1.7) with $(n, m) \ne (n_1, m_1)$, $n > \min\{k+2, n_1+1\}$, $n_1 \ge 2$, $m > m_1 \ge 1$, and $k \ge 4$, we then have that $n < 4 \times 10^{42} k^{11} (\log k)^7$.

# 5. Reduction of the Bounds on n

## 5.1. The cutoff k

We have from the above lemma that Baker's method gives

$$n < 4 \times 10^{42} k^{11} (\log k)^7.$$

By imposing that the above amount is at most $2^{k/2}$, we get

$$4 \times 10^{42} k^{11} (\log k)^7 < 2^{k/2}.$$

The inequality above holds for $k > 600$.

We now reduce the bounds and to do so we make use of Lemma 2.3 several times.
## 5.2. The case of small k

We now treat the cases when $k \in [4, 600]$. First, we consider Eq. (3.1) which is equivalent to (1.7). For $k \in [4, 600]$ and $n \in [3, 600]$, consider the sets

$$F_{n,k} := \{F_n^{(k)} - F_{n_1}^{(k)} (\text{mod } 10^{20}) : n \in [3, 600], n_1 \in [2, n-1]\}$$

and

$$D_{n,k} := \{3^m - 3^{m_1} (\text{mod } 10^{20}) : m \in [2, 600], m_1 \in [1, m-1]\}.$$

With the help of *Mathematica*, we intersected these two sets and found the only solutions listed in Theorem 1.1.

Next, we note that for these values of $k$, Lemma 4.1 gives us absolute upper bounds for $n$. However, these upper bounds are so large that we wish to reduce them to a range where the solutions can be easily identified by a computer. To do this, we return to (4.3) and put

$$\Gamma := (n-1) \log \alpha - m \log 3 + \log(f_k(\alpha)).$$

For technical reasons we assume that $\min\{n - n_1, m - m_1\} \ge 20$. In the case that this condition fails, we consider one of the following inequalities instead:

(i) if $n - n_1 < 20$ but $m - m_1 \ge 20$, we consider (4.4);

(ii) if $n - n_1 \ge 20$ but $m - m_1 < 20$, we consider (4.5);

(iii) if $n - n_1 < 20$ but $m - m_1 < 20$, we consider (4.7).

We start by considering (4.3). Note that $\Gamma \ne 0$; thus we distinguish the following two cases. If $\Gamma > 0$, then $e^\Gamma - 1 > 0$, then from (4.3) we get

$$0 < \Gamma < e^\Gamma - 1 < \max\{\alpha^{n_1-n+6}, 3^{m_1-m+1}\}.$$

Next we suppose that $\Gamma < 0$. Since $\Lambda = |e^\Gamma - 1| < \frac{1}{2}$, we get that $e^{|\Gamma|} < 2$. Therefore,

$$0 < |\Gamma| \le e^{|\Gamma|} - 1 = e^{|\Gamma|} |e^\Gamma - 1| < 2 \max\{\alpha^{n_1-n+6}, 3^{m_1-m+1}\}.$$

Therefore, in any case, the following inequality holds:

$$0 < |\Gamma| < 2 \max\{\alpha^{n_1-n+6}, 3^{m_1-m+1}\}. \qquad (5.1)$$

By replacing $\Gamma$ in the above inequality by its formula and dividing through by $\log 3$, we then conclude that

$$0 < \left| (n-1) \left( \frac{\log \alpha}{\log 3} \right) - m + \frac{\log(f_k(\alpha))}{\log 3} \right| < \max \left\{ (2\alpha^6) \cdot \alpha^{-(n-n_1)}, \frac{6}{\log 3} \cdot 3^{-(m-m_1)} \right\}.$$

Then, we apply Lemma 2.3 with the following data:

$$k \in [4, 600], \quad \tau_k := \frac{\log \alpha}{\log 3}, \quad \mu_k := \frac{\log(f_k(\alpha))}{\log 3},$$

$$(A_k, B_k) := (2\alpha^6, \alpha) \text{ or } \left(\frac{6}{\log 3}, 3\right).$$
Next, we put $M_k := [4 \times 10^{42}k^{11}(\log k)^7]$, which is the absolute upper bound on $n$ by Lemma 4.1. An intensive computer search in *Mathematica* revealed that the maximum value of $\lfloor\log(2\alpha^6q/\varepsilon)/\log\alpha\rfloor$ is < 600 and the maximum value of $\lfloor\log((6/\log 3)q/\varepsilon)/\log 3\rfloor$ is < 375. Thus, either

$$n - n_1 < \frac{\log(2\alpha^6 q/\varepsilon)}{\log \alpha} < 600, \quad \text{or} \quad m - m_1 < \frac{\log((6/\log 3)q/\varepsilon)}{\log 3} < 375.$$

Therefore, we have that either $n - n_1 \le 600$ or $m - m_1 \le 375$.

Now, let us assume that $n - n_1 \le 600$. In this case, we consider the inequality (4.4) and assume that $m - m_1 \ge 20$. Then we put

$$\Gamma_1 := (n_1 - 1) \log \alpha - m \log 3 + \log(f_k(\alpha)(\alpha^{n-n_1} - 1)).$$

By similar arguments as in the previous step for proving (5.1), from (4.4) we get

$$0 < |\Gamma_1| < \frac{6}{3^{m-m_1}},$$

and replacing $\Gamma_1$ with its formula and dividing through by $\log 3$ give

$$0 < \left| (n_1 - 1) \left( \frac{\log \alpha}{\log 3} \right) - m + \frac{\log(f_k(\alpha)(\alpha^{n-n_1} - 1))}{\log 3} \right| < \frac{6}{\log 3} \cdot 3^{-(m-m_1)}. \quad (5.2)$$

As before, we keep the same $\tau_k, M_k, (A_k, B_k) := ((6/\log 3), 3)$ and put

$$\mu_{k,l} := \frac{\log(f_k(\alpha)(\alpha^l - 1))}{\log 3}, \quad k \in [4, 600], \quad l := n - n_1 \in [1, 600].$$

We apply Lemma 2.3 to the inequality (5.2) with the above data. A computer search in *Mathematica* revealed that the maximum value of $\lfloor\log(Aq/\varepsilon)/\log B\rfloor$ over the values of $k \in [4, 600]$ and $l \in [1, 600]$ is < 377. Hence, $m - m_1 \le 377$.

Next, we assume that $m - m_1 \le 375$. Here, we consider the inequality (4.5) and also assume that $n - n_1 \ge 20$. We put

$$\Gamma_2 := (n - 1) \log \alpha - m_1 \log 3 + \log(f_k(\alpha)/(3^{m-m_1} - 1)).$$

Thus, by the same arguments as before, we get

$$0 < |\Gamma_2| < \frac{2\alpha^6}{\alpha^{n-n_1}}.$$

By substituting for $\Gamma_2$ with its formula and dividing through by $\log 3$ in the above inequality, we get

$$0 < \left| (n-1) \left( \frac{\log \alpha}{\log 3} \right) - m_1 + \frac{\log(f_k(\alpha)/(3^{m-m_1}-1))}{\log 3} \right| < \frac{2\alpha^6}{\log 3} \cdot \alpha^{-(n-n_1)}.$$

As before, we apply Lemma 2.3 with the same $\tau_k, M_k, (A_k, B_k) := (2\alpha^6/\log 3, \alpha)$ and put

$$\mu_{k,j} := \frac{\log(f_k(\alpha)/(3^{m-m_1}-1))}{\log 3}, \quad k \in [4, 600],$$

$$j := m - m_1 \in [1, 375].$$
A computer search with *Mathematica* revealed that the maximum value of $[\log(Aq/\epsilon)/\log B]$, for $k \in [4, 600]$ and $j \in [1, 375]$ is $< 603$. Hence, $n - n_1 \le 603$.

To conclude the above computations, first we obtained that either $n - n_1 \le 600$ or $m - m_1 \le 375$. If $n - n_1 \le 600$, then $m - m_1 \le 377$, and if $m - m_1 \le 375$, then $n - n_1 \le 603$. Therefore, we can conclude that we always have

$$n - n_1 \le 603 \quad \text{and} \quad m - m_1 \le 377.$$

Finally, we go to (4.7) and put

$$\Gamma_3 := (n_1 - 1) \log \alpha - m_1 \log 3 + \log \left( \frac{f_k(\alpha)(\alpha^{n-n_1} - 1)}{3^{m-m_1} - 1} \right).$$

Since $n > 600$, from (4.7) we can conclude that

$$0 < |\Gamma_3| < \frac{2 \cdot 3^5}{3^{0.8n}}.$$

Hence, by substituting for $\Gamma_3$ by its formula and dividing through by $\log 3$, we get

$$0 < \left| (n_1 - 1) \left( \frac{\log \alpha}{\log 3} \right) - m_1 + \frac{\log (f_k(\alpha)(\alpha^{n-n_1} - 1)/(3^{m-m_1} - 1))}{\log 3} \right| < 1328 \cdot 3^{-0.8n}.$$

We apply Lemma 2.3 with the same $\tau_k, M_k, (A_k, B_k) := (1328, 3)$, $k \in [4, 600]$, and put

$$\mu_{k,l,j} := \frac{\log(f_k(\alpha)(\alpha^l - 1)/(3^j - 1))}{\log 3}, \quad l := n - n_1 \in [1, 603], \\ j := m - m_1 \in [1, 377].$$

A computer search in *Mathematica* revealed that the maximum value of $[\log(1328q/\epsilon)/\log 3]$, for $k \in [4, 600]$, $l \in [1, 603]$ and $j \in [1, 377]$ is $< 378$. Hence, $n < 473$, which contradicts the assumption that $n > 500$ in the previous section.

### 5.3. The case of large k

We now assume that $k > 600$. Note that for these values of $k$ we have

$$n < 4 \times 10^{42} k^{11} (\log k)^7.$$

Since, $n \ge k + 2$, we have that $n \ge 602$. The following lemma is useful.

**Lemma 5.1.** For $1 \le n < 2^{k/2}$ and $k \ge 10$, we have

$$F_n^{(k)} = 2^{n-2}(1 + \zeta) \quad \text{where} \quad |\zeta| < \frac{5}{2^{k/2}}.$$

**Proof.** When $n \le k + 1$, we have $F_n^{(k)} = 2^{n-2}$ so we can take $\zeta := 0$. So, assume $k + 2 \le n < 2^{k/2}$. It follows from [3, (1.8)] that

$$|f_k(\alpha)\alpha^{n-1} - 2^{n-2}| < \frac{2^n}{2^{k/2}}.$$
By (2.3), we also have $|F_n^{(k)} - f_k(\alpha)\alpha^{n-1}| < 1/2$. Thus,

$$ 
\begin{aligned}
|F_n^{(k)} - 2^{n-2}| &\le |f_k(\alpha)\alpha^{n-1} - 2^{n-2}| + |F_n^{(k)} - f_k(\alpha)\alpha^{n-1}| \\
&< \frac{2^n}{2^{k/2}} + \frac{1}{2} = \frac{2^n}{2^{k/2}} \left(1 + \frac{1}{2^{n-k/2+1}}\right) \le \frac{2^n}{2^{k/2}} \left(1 + \frac{1}{2^{k/2+3}}\right) \\
&< \frac{2^n \cdot 1.25}{2^{k/2}} = \left(\frac{5}{2^{k/2}}\right) 2^{n-2}.
\end{aligned}
$$

By the above lemma, we can rewrite (3.1) as

$$ 2^{n-2}(1 + \zeta) - 2^{n_1-2}(1 + \zeta_1) = 3^m - 3^{m_1}, \quad \max\{|\zeta|, |\zeta_1|\} < \frac{5}{2^{k/2}}. $$

So,

$$ 
\begin{aligned}
|2^{n-2} - 3^m| &= | - \zeta \cdot 2^{n-2} + 2^{n_1-2}(1 + \zeta_1) - 3^{m_1} | \\
&\le 2^{n-2} \left( \frac{5}{2^{k/2}} \right) + 2^{n_1-2} \left( 1 + \frac{5}{2^{k/2}} \right) + 3^{m_1}
\end{aligned}
\quad (5.3) $$

Next, we have

$$ 2^{n-2} > F_n^{(k)} - F_{n_1}^{(k)} = 3^m - 3^{m_1} \ge 2 \cdot 3^{m-1}, \quad \text{so } 2^{n-2}/3^m > 2/3. $$

Further,

$$ 
\begin{aligned}
3^m > 3^m - 3^{m_1} &= F_n^{(k)} - F_{n_1}^{(k)} \ge F_n^{(k)} - F_{n-1}^{(k)} \\
&\ge F_{n-2}^{(k)} > 2^{n-4} \left(1 - \frac{5}{2^{k/2}}\right) \\
&> 2^{n-4} \left(\frac{27}{32}\right) \quad (k > 10),
\end{aligned}
$$

so

$$ \frac{128}{27} > \frac{2^{n-2}}{3^m} > \frac{2}{3}. $$

Going back to (5.3), we have

$$ |3^m 2^{-(n-2)} - 1| < \frac{5}{2^{k/2}} + \frac{1.25}{2^{n-n_1}} + \frac{3^{m_1}}{(2/3)3^m} = \frac{5}{2^{k/2}} + 1.5 \left( \frac{1}{2^{n-n_1}} + \frac{1}{3^{m-m_1}} \right). $$

Thus,

$$ |3^m 2^{-(n-2)} - 1| < 8 \max \left\{ \frac{1}{2^{n-n_1}}, \frac{1}{3^{m-m_1}}, \frac{1}{2^{k/2}} \right\}. \quad (5.4) $$

We now apply Theorem 2.2 on the left-hand side of (5.4) with the data

$$ \Gamma := 3^m 2^{-(n-2)} - 1, \quad t := 2, \quad \gamma_1 := 3, \quad \gamma_2 := 2, \quad b_1 := m, \quad b_2 := -(n-2). $$

It is clear that $\Gamma \ne 0$, otherwise we would get $3^m = 2^{n-2}$ which is a contradiction since $3^m$ is odd while $2^{n-2}$ is even. We consider the field $\mathbb{K} = \mathbb{Q}$, in this case $D = 1$.
Since $h(\gamma_1) = h(3) = \log 3$ and $h(\gamma_2) = h(2) = \log 2$, we can take $A_1 := \log 3$ and $A_2 := \log 2$. We also take $B := n$. Then, by Theorem 2.2, the left-hand side of (5.4) is bounded below as

$$ \log |\Gamma| > -5.86 \times 10^8 (1 + \log n). $$

By comparing with (5.4), we get

$$ \begin{aligned} & \min\{(n - n_1 - 3) \log 2, (m - m_1 - 2) \log 3, (k/2 - 3) \log 2\} \\ & < 5.86 \times 10^8 (1 + \log n), \end{aligned} $$

which implies that

$$ \min\{(n - n_1) \log 2, (m - m_1) \log 3, (k/2) \log 2\} < 5.88 \times 10^8 (1 + \log n). $$

Now the argument is split into four cases.

**Case 5.3.1.** $\min\{(n - n_1) \log 2, (m - m_1) \log 3, (k/2) \log 2\} = (k/2) \log 2$.

In this case, we have

$$ (k/2) \log 2 < 5.88 \times 10^8 (1 + \log n), $$

which implies that

$$ k < 1.70 \times 10^9 (1 + \log n). $$

**Case 5.3.2.** $\min\{(n - n_1) \log 2, (m - m_1) \log 3, (k/2) \log 2\} = (n - n_1) \log 2$.

We rewrite (3.1) as

$$ \begin{aligned} |3^m - 2^{n_1-2}(2^{n-n_1}-1)| &= |3^{m_1} + 2^{n-2}\zeta - 2^{n_1-2}\zeta_1| \\ &< 3^{m_1} + 2^{n-2}\left(\frac{10}{2^{k/2}}\right), \end{aligned} $$

which implies that

$$ |3^m 2^{-n_1} (2^{n-n_1}-1)^{-1} - 1| < 20 \max \left\{ \frac{1}{3^{m-m_1}}, \frac{1}{2^{k/2}} \right\}. \quad (5.5) $$

We now apply Matveev's theorem, Theorem 2.2 on the left-hand side of (5.5) to

$$ \Gamma_1 = 3^m 2^{-(n_1-2)} (2^{n-n_1}-1)^{-1} - 1, $$

with the data

$$ t := 3, \quad \gamma_1 := 3, \quad \gamma_2 := 2, \quad \gamma_3 := 2^{n-n_1}-1, $$

$$ b_1 := m, \quad b_2 := -(n_1 - 2), \quad b_3 := -1. $$

Note that $\Gamma_1 \neq 0$. Otherwise, $3^m = 2^{n-2} - 2^{n_1-2}$, so $n_1 = 2$, and $2^{n-2} - 3^m = 1$, so $n \le 4$ by classical results on Catalan's equation, which is a contradiction because $n \ge k+2 > 602$. We use the same values, $A_1 := \log 3$, $A_2 := \log 2$, $B := n$ as in the previous step. In order to find $A_3$, note that

$$ h(\gamma_3) = h(2^{n-n_1}-1) \le (n - n_1 + 1) \log 2 < 5.90 \times 10^8 (1 + \log n). $$
So, we take $A_3 := 5.90 \times 10^8(1 + \log n)$. By Theorem 2.2, we have

$$ \log |\Gamma_1| > -6.43 \times 10^{19}(1 + \log n)^2. $$

By comparing with (5.5), we get

$$ \min\{(m - m_1 - 3) \log 3, (k/2 - 5) \log 2\} < 6.43 \times 10^{19}(1 + \log n)^2, $$

which implies that

$$ \min\{(m - m_1) \log 3, (k/2) \log 2\} < 6.44 \times 10^{19}(1 + \log n)^2. $$

At this step, we have that either

$$ (m - m_1) \log 3 < 6.44 \times 10^{19}(1 + \log n)^2 $$

or

$$ k < 1.86 \times 10^{20}(1 + \log n)^2. $$

**Case 5.3.3.** $\min\{(n - n_1) \log 2, (m - m_1) \log 3, (k/2) \log 2\} = (m - m_1) \log 3$.

We rewrite (3.1) as

$$ \begin{aligned} & |(3^{m_1}(3^{m-m_1}-1)-2^{n-2}| = |2^{n-2}\zeta - 2^{n_1-2}(1+\zeta_1)| \\ & < 2^{n-2}\left(\frac{5}{2^{k/2}}\right) + 2^{n_1-2}\left(1+\frac{5}{2^{k/2}}\right), \end{aligned} $$

which implies that

$$ |3^{m_1}(3^{m-m_1}-1)2^{-(n-2)} - 1| < 20 \max \left\{ \frac{1}{2^{n-n_1}}, \frac{1}{2^{k/2}} \right\}. \quad (5.6) $$

We again apply Matveev's theorem, Theorem 2.2 on the left-hand side of (5.5) which is

$$ \Gamma_2 = 3^{m_1} 2^{-(n-2)} (3^{m-m_1} - 1) - 1, $$

with the data

$$ t := 3, \quad \gamma_1 := 3, \quad \gamma_2 := 2, \quad \gamma_3 := (3^{m-m_1}-1), $$

$$ b_1 := m_1, \quad b_2 := -(n-2), \quad b_3 := 1. $$

Note that $\Gamma_2 \neq 0$. Otherwise, $3^m - 3^{m_1} = 2^{n-2}$, which is impossible since the left-hand side is a multiple of 3 and the right-hand side is not. We use the same values, $A_1 := \log 3$, $A_2 := \log 2$, $B := n$ as in the previous steps. In order to determine $A_3$, note that

$$ h(\gamma_3) = h(3^{m-m_1}-1) \le (m - m_1 + 1) \log 3 < 5.90 \times 10^8(1 + \log n). $$

So, we take $A_3 := 5.90 \times 10^8(1 + \log n)$. By Theorem 2.2, we have the lower bound

$$ \log |\Gamma_2| > -6.43 \times 10^{19}(1 + \log n)^2. $$
By comparing with (5.6), we get

$$ \min\{(n - n_1 - 5) \log 3, (k/2 - 5) \log 2\} < 6.43 \times 10^{19} (1 + \log n)^2, $$

which implies that

$$ \min\{(n - n_1) \log 3, (k/2) \log 2\} < 6.44 \times 10^{19} (1 + \log n)^2. $$

As before, at this step we have that either

$$ (n - n_1) \log 3 < 6.44 \times 10^{19} (1 + \log n)^2 $$

or

$$ k < 1.86 \times 10^{20} (1 + \log n)^2. $$

Therefore, in all the three cases above, we obtained

$$ \min\{(n - n_1) \log 2, (m - m_1) \log 3, (k/2) \log 2\} < 5.88 \times 10^8 (1 + \log n), $$

$$ \max\{(n - n_1) \log 2, (m - m_1) \log 3, (k/2) \log 2\} < 6.44 \times 10^{19} (1 + \log n)^2. $$

**Case 5.3.4.** ($k/2) \log 2 > 6.44 \times 10^{19} (1 + \log n)^2$.

From the previous analysis, we conclude that one of $(n - n_1) \log 2$ and $(m - m_1) \log 3$ is bounded by $5.88 \times 10^8 (1 + \log n)$ and the other one by $6.44 \times 10^{19} (1 + \log n)^2$. We rewrite (3.1) as

$$ |3^{m_1}(3^{m-m_1}-1)-2^{n_1-2}(2^{n-n_1}-1)| = |\zeta| \cdot 2^{n-2} + |\zeta_1| \cdot 2^{n_1-2} \le 2^{n-2} \left(\frac{10}{2^{k/2}}\right), $$

which implies that

$$ \left| 3^{m_1} 2^{-(n_1-2)} \left( \frac{3^{m-m_1}-1}{2^{n-n_1}-1} \right) - 1 \right| < \frac{20}{2^{k/2}}. \quad (5.7) $$

We apply Matveev's Theorem to

$$ \Gamma_3 = 3^{m_1} 2^{-(n_1-2)} \left( \frac{3^{m-m_1}-1}{2^{n-n_1}-1} \right) - 1, $$

with the data

$$ t := 3, \quad \gamma_1 := 3, \quad \gamma_2 := 2, \quad \gamma_3 := \left( \frac{3^{m-m_1}-1}{2^{n-n_1}-1} \right), $$

$$ b_1 := m_1, \quad b_2 := -(n_1 - 2), \quad b_3 := 1. $$

Note that $\Gamma_3 \ne 0$, otherwise, we get $2^n - 3^m = 2^{n_1} - 3^{m_1}$ which is impossible by Lemma 3.1.

As before we take $B := n$, $A_1 := \log 3$, $A_2 := \log 2$. In order to determine an acceptable value for $A_3$, note that

$$ \begin{aligned} h(\gamma_3) &\le h(3^{m-m_1}-1) + h(2^{n-n_1}-1) < (m-m_1+1)\log 3 + (n-n_1+1)\log 2 \\ &< 2 \times 6.46 \times 10^{19} (1 + \log n)^2 < 1.30 \times 10^{20} (1 + \log n)^2. \end{aligned} $$
Thus, we take $A_3 := 1.30 \times 10^{20}(1 + \log n)^2$. By Theorem 2.2, we have

$$ \log |\Gamma_3| > -1.86 \times 10^{31}(1 + \log n)^3. $$

By comparing with (5.7), we get

$$ (k/2 - 5) \log 2 < 1.86 \times 10^{31}(1 + \log n)^3, $$

which implies that

$$ k < 5.42 \times 10^{31}(1 + \log n)^3. \qquad (5.8) $$

Thus, inequality (5.8) holds in all four cases. Since $n < 4 \times 10^{42}k^{11}(\log k)^7$, then

$$ k < 5.42 \times 10^{31}(1 + \log(4 \times 10^{42}k^{11}(\log k)^7))^3, $$

which gives the absolute upper bounds

$$ k < 8.631 \times 10^{40} < 10^{41} $$

and

$$ m < n < 3.44 \times 10^{506} < 10^{507}. $$

We record what we have proved.

**Lemma 5.2.** We have

$$ k < 10^{41} \quad \text{and} \quad m < 10^{507}. $$

## 5.4. The final reduction

The previous bounds are too large, so we need to reduce them by applying a Baker-Davenport reduction procedure. First, we go to (5.4) and let

$$ z := m \log 3 - (n - 2) \log 2. $$

Assume $m - m_1 > 1066$, $n - n_1 > 1690$ and $k > 600$. Then, we note that (5.5) can be rewritten as

$$ |e^z - 1| < \max\{2^{n_1-n+3}, 3^{m_1-m+2}, 2^{-k/2+3}\}. $$

If $z > 0$, then $e^z - 1 > 0$, so we obtain

$$ 0 < z < e^z - 1 < \max\{2^{n_1-n+3}, 3^{m_1-m+2}, 2^{-k/2+3}\}. $$

Suppose now that $z < 0$. Since $\Gamma = |e^z - 1| < 1/2$, we get that $e^{|z|} < 2$. Thus,

$$ 0 < |z| \le e^{|z|} - 1 = e^{|z|} |e^z - 1| < 2 \max\{2^{n_1-n+3}, 3^{m_1-m+2}, 2^{-k/2+3}\}. $$

Therefore, in any case we have that the inequality

$$ 0 < |z| < 2 \max\{2^{n_1-n+3}, 3^{m_1-m+2}, 2^{-k/2+3}\} $$
always holds. By replacing $z$ in the above inequality by its formula and dividing through by $m \log 2$, we get that

$$0 < \left| \frac{\log 3}{\log 2} - \frac{n}{m} \right| < \max \left\{ \frac{24}{2^{n-n_1}m}, \frac{26}{3^{m-m_1}m}, \frac{24}{2^{k/2}m} \right\}.$$

Then

$$\max \left\{ \frac{24}{2^{n-n_1}m}, \frac{26}{3^{m-m_1}m}, \frac{24}{2^{k/2}m} \right\} < \frac{1}{2m^2},$$

because $m < 10^{507}$. By the Legendre criterion (Lemma 2.4), it follows that $n/m$ is a convergent of $\log 3/\log 2$. So $n/m$ is of the form $p_l/q_l$ for some $l = 0, 1, 2, \dots, 972$. Then $n/m = p_l/q_l$ implies that $m = d q_l$ for some $d \ge 1$. Thus,

$$\frac{1}{(a_{l+1} + 2)q_k q_{l+1}} < \left| \frac{\log 3}{\log 2} - \frac{p_l}{q_l} \right| < \max \left\{ \frac{24}{2^{n-n_1} d q_l}, \frac{26}{3^{m-m_1} d q_l}, \frac{24}{2^{k/2} d q_l} \right\}.$$

Since $\max\{a_{l+1} : l = 0, 1, 2, \dots, 972\} = 3308$, we get that

$$\min\{2^{n-n_1}, 3^{m-m_1}, 2^{k/2}\} \le 26 \cdot 3310q_{973}.$$

With the help of *Mathematica*, we have $q_{973} \approx 1.6834 \times 10^{507}$. We then conclude that one of the following inequalities holds:

$$n - n_1 < 1690, \quad m - m_1 < 1066, \quad k < 3380.$$

Suppose first that $m - m_1 > 10$ and $k \ge 20$, we go back to (5.5) and let

$$z_1 := m \log 3 - (n_1 - 2) \log 2 - \log(2^{n-n_1} - 1).$$

Then we note that (5.5) can be rewritten as

$$|e^{z_1} - 1| < \max\{3^{m_1-m+3}, 2^{-k/2+5}\}.$$

This implies that

$$0 < |z_1| < 2 \max\{3^{m_1-m+3}, 2^{-k/2+5}\}.$$

This also holds when $m - m_1 < 10$ and $k < 20$. By substituting for $z_1$ and dividing through by $\log 2$, we get

$$0 < \left| m \left( \frac{\log 3}{\log 2} \right) - (n_1 - 2) + \frac{\log(1/(2^{n-n_1} - 1))}{\log 2} \right| < \max\{98 \cdot 3^{-(m-m_1)}, 94 \cdot 2^{-k/2}\}.$$

We put

$$\tau := \frac{\log 3}{\log 2}, \quad \mu := \frac{\log(1/(2^{n-n_1} - 1))}{\log 2}, \quad (A, B) := (78, 3) \text{ or } (94, 2),$$

where $n - n_1 \in [1, 1690]$. We take $M := 10^{507}$. A computer search in *Mathematica* reveals that $q = q_{977} \approx 5.708 \times 10^{510} > 6M$ and the minimum positive value of $\varepsilon := \|\mu q\| - M\|\tau q\| > 0.0186$. Thus, Lemma 2.3 tells us that either $m - m_1 \le 1078$ or $k \le 3418$.
Next, we suppose that $n - n_1 > 10$, $k > 20$ and go to (5.6) and let

$$z_2 := m_1 \log 3 - (n - 2) \log 2 + \log(3^{m-m_1} - 1).$$

Then we also note that (5.6) can be rewritten as

$$|e^{z_2} - 1| < \max\{2^{n_1-n+5}, 2^{-k/2+5}\}.$$

This gives

$$0 < |z_2| < 2 \max\{2^{n_1-n+5}, 2^{-k/2+5}\}.$$

This also holds for $n - n_1 < 10$ and $k < 20$ as well. By substituting for $z_2$ and dividing through by $\log 2$, we get

$$0 < \left| m_1 \left( \frac{\log 3}{\log 2} \right) - (n-2) + \frac{\log(3^{m-m_1}-1)}{\log 2} \right| < \max\{94 \cdot 2^{-(n-n_1)}, 94 \cdot 2^{-k/2}\}.$$

We put

$$\tau := \frac{\log 3}{\log 2}, \quad \mu := \frac{\log(3^{m-m_1}-1)}{\log 2}, \quad (A, B) := (94, 2),$$

where $m - m_1 \in [1, 1066]$. We keep the same $M$ and $q$ as in the previous step. A computer search in *Mathematica* reveals that the minimum positive value of $\varepsilon := \|\mu q\| - M \|\tau q\| > 0.0372$. Thus, Lemma 2.3 tells us that either $n - n_1 \le 1708$ or $k \le 3416$.

Finally, we assume that $k > 20$ and go to (5.7) and let

$$z_3 := m_1 \log 3 - (n_1 - 2) \log 2 - \log\left(\frac{3^{m-m_1}-1}{2^{n-n_1}-1}\right).$$

We note that (5.7) can be rewritten as

$$|e^{z_3} - 1| < 2^{-k/2+5}.$$

This gives

$$0 < |z_3| < 2^{-k/2+6},$$

which also holds when $k < 20$. By substituting for $z_3$ and dividing through by $\log 2$, we get

$$0 < \left| m_1 \left( \frac{\log 3}{\log 2} \right) - (n_1 - 2) + \frac{\log\left(\frac{3^{m-m_1}-1}{2^{n-n_1}-1}\right)}{\log 2} \right| < 94 \cdot 2^{-k/2}.$$

We put

$$\tau := \frac{\log 3}{\log 2}, \quad \mu := \frac{\log\left(\frac{3^{m-m_1}-1}{2^{n-n_1}-1}\right)}{\log 2}, \quad (A, B) := (94, 2),$$

where $n - n_1 \in [1, 1078]$ and $m - m_1 \in [1, 1074]$. We keep the same $M$ and $q$ as before. A computer search in *Mathematica* reveals that the minimum positive value of $\varepsilon := \|\mu q\| - M \|\tau q\| > 0.00058$. Thus, Lemma 2.3 tells us that $k \le 3428$.

Therefore, in all cases we found out that $k < 3428$ which gives that $n < 7.2741 \times 10^{87} < 10^{88}$. These bounds are still too large. We repeat the above procedure
<table><caption>Table 1. Computation results.</caption><thead><tr><th></th><th><i>M</i></th><th><i>n</i> − <i>n</i><sub>1</sub> ≤</th><th><i>m</i> − <i>m</i><sub>1</sub> ≤</th><th><i>k</i> ≤</th></tr></thead><tbody><tr><td>1</td><td>10<sup>507</sup></td><td>1708</td><td>1074</td><td>3428</td></tr><tr><td>2</td><td>10<sup>88</sup></td><td>319</td><td>197</td><td>662</td></tr><tr><td>3</td><td>10<sup>80</sup></td><td>287</td><td>180</td><td>590</td></tr><tr><td>4</td><td>10<sup>79</sup></td><td>282</td><td>180</td><td>584</td></tr><tr><td>5</td><td>10<sup>79</sup></td><td>282</td><td>180</td><td>584</td></tr></tbody></table>

several times by adjusting the values of *M* with respect to the new bounds of *n*. We summarize the data for the iterations performed in Table 1.

From the data displayed in Table 1, it is evident that after four times of the iteration, the upper bound on *k* stabilizes at 584. Hence, *k* < 600 which contradicts our assumption that *k* > 600. Therefore, we have no further solutions to the Diophantine equation (1.7) with *k* > 600.

## Acknowledgments

Open Access funding provided by the Austrian Science Fund (FWF). M. D. was supported by the FWF projects: F5510-N26 — Part of the special research program (SFB), “Quasi-Monte Carlo Methods: Theory and Applications” and W1230 — “Doctoral Program Discrete Mathematics”. F. L. was also supported by grant CPRR160325161141 from the NRF of South Africa and grant RTNUM19 from CoEMaSS, Wits, South Africa. Part of the work in this paper was done when both authors visited the Max Planck Institute for Mathematics Bonn, in March 2018 and the Institut de Mathématiques de Bordeaux, Université de Bordeaux, in May 2019. They thank these institutions for hospitality and fruitful working environments.

## 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. (2) **20** (1969) 129–137.

[2] A. Baker and G. Wüstholz, *Logarithmic Forms and Diophantine Geometry*, Vol. 9 New Mathematical Monographs (Cambridge University Press, 2007).

[3] J. J. Bravo, C. A. Gómez and F. Luca, On the distance between generalised Fibonacci numbers, *Colloq. Math.* **140**(1) (2015) 107–118.

[4] J. J. Bravo and F. Luca, Powers of two in generalized Fibonacci sequences, *Rev. Colombiana Mat.* **46**(1) (2012) 67–79.

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

[6] J. J. Bravo, F. Luca and K. Yazán. On Pillai's problem with Tribonacci numbers and powers of 2, *Bull. Korean Math. Soc.* **54**(3) (2017) 1069–1080.

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

[8] K. C. Chim, I. Pink and V. Ziegler, On a variant of Pillai's problem, *Int. J. Number Theory* **13**(7) (2017) 1711–1727.
[9] K. C. Chim, I. Pink and V. Ziegler, On a variant of Pillai's problem II, *J. Number Theory* **183** (2018) 269–290.

[10] M. Ddamulira, On the problem of Pillai with Fibonacci numbers and powers of 3, *Bol. Soc. Mat. Mex.* (2019), https://doi.org/10.1007/s40590-019-00263-1.

[11] M. Ddamulira, On the problem of Pillai with Tribonacci numbers and powers of 3, *J. Integer Seq.* **22**(5) (2019) Art. 19.5.6, 14 pp.

[12] M. Ddamulira, C. A. Gómez and F. Luca, On a problem of Pillai with *k*-generalized Fibonacci numbers and powers of 2, *Monatsh. Math.* **187**(4) (2018) 635–664.

[13] M. Ddamulira, F. Luca and M. Rakotomalala. On a problem of Pillai with Fibonacci numbers and powers of 2, *Proc. Indian Acad. Sci. Math. Sci.* **127**(3) (2017) 411–421.

[14] G. P. B. Dresden and Z. Du, A simplified Binet formula for *r*-generalized Fibonacci numbers, *J. Integer Seq.* **17**(4) (2014), Art. 14.4.7, 9pp.

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

[16] S. Gúzman Sánchez and F. Luca, Linear combinations of factorials and *s*-units in a binary recurrence sequence, *Ann. Math. Qué.* **38**(2) (2014) 169–188.

[17] S. Hernández Hernández, F. Luca and L. M. Rivera, On Pillai's problem with the Fibonacci and Pell sequences, *Bol. Soc. Mat. Mex.* **25**(3) (2019) 495–507.

[18] M. O. Hernane, F. Luca, S. E. Rihane and A. Togbé, On Pillai's problem with Pell numbers and powers of 2, *Hardy-Ramanujan J.* **41** (2018) 22–31.

[19] A. Herschfeld, The equation $2^x - 3^y = d$, *Bull. Amer. Math. Soc.* **41**(9) (1935) 631.

[20] A. Herschfeld, The equation $2^x - 3^y = d$, *Bull. Amer. Math. Soc.* **42**(4) (1936) 231–234.

[21] 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**(6) (2000) 125–180 (in Russian); *Izv. Math.* **64**(6) (2000) 1217–1269.

[22] P. Mihăilescu, Primary cyclotomic units and a proof of Catalan's conjecture, *J. Reine Angew. Math.* **572** (2006) 167–195.

[23] S. S. Pillai, On $a^x - b^y = c$, *J. Indian Math. Soc. (N.S.)* **2** (1936) 119–122.

[24] S. S. Pillai, A correction to the paper: "On $a^x - b^y = c$", *J. Indian Math. Soc. (N.S.)* **2** (1937) 215.

[25] R. J. Stroeker and R. Tijdeman, Diophantine equations, in *Computational Methods in Number Theory, Part II*, Mathematics Centre Tracts, Vol. 155 (Mathematics Centrum, Amsterdam, 1982), pp. 321–369.