# Multimodal Language Models for Domain-Specific Procedural Video
Summarization

Nafisa Hussain  University of California, Santa CruzSanta CruzUSA
<EMAIL_ADDRESS>
###### Abstract.

Videos serve as a powerful medium to convey ideas, tell stories, and provide
detailed instructions, especially through long-format tutorials. Such
tutorials are valuable for learning new skills at one’s own pace, yet they can
be overwhelming due to their length and dense content. Viewers often seek
specific information, like precise measurements or step-by-step execution
details, making it essential to extract and summarize key segments
efficiently. An intelligent, time-sensitive video assistant capable of
summarizing and detecting highlights in long videos is highly sought after.
Recent advancements in Multimodal Large Language Models offer promising
solutions to develop such an assistant. Our research explores the use of
multimodal models to enhance video summarization and step-by-step instruction
generation within specific domains. These models need to understand temporal
events and relationships among actions across video frames. Our approach
focuses on fine-tuning TimeChat to improve its performance in specific
domains: cooking and medical procedures. By training the model on domain-
specific datasets like Tasty for cooking and MedVidQA for medical procedures,
we aim to enhance its ability to generate concise, accurate summaries of
instructional videos. We curate and restructure these datasets to create high-
quality video-centric instruction data. Our findings indicate that when
finetuned on domain-specific procedural data, TimeChat can significantly
improve the extraction and summarization of key instructional steps in long-
format videos. This research demonstrates the potential of specialized
multimodal models to assist with practical tasks by providing personalized,
step-by-step guidance tailored to the unique aspects of each domain.

Large Vision Language Models, Multimodality, Fine-tuning, Large Language
Models, Visual Question Answering, Instruction Fine-Tuning

††ccs: Computing methodologies Video summarization

##  1\. Introduction

Various ideas and concepts can be expressed through the medium of videos.
Longer format videos provide the means to tell stories, teach topics, and
provide detailed instructions. The means to provide in-depth tutorials through
visual demonstrations of steps in succession to aid in the visual
understanding of procedures greatly benefits viewers whose intent is to learn
new skills and tasks at their own time and pace. However, long video tutorials
oftentimes can be lengthy and dense in content, making it both time-consuming
and frustrating for individuals to sift through for key instructions. The
information needs of viewers can vary from looking for correct measurements of
materials to understanding tactically how to execute a step. Users’ needs can
be satisfied by localizing and retrieving video highlights and concisely
summarizing the activity or event from highlighted clips. An intelligent,
time-sensitive video assistant capable of summarizing and detecting highlights
within long-format videos is a longstanding pursuit for developers.
Advancements in Large Language Model capabilities show promise in developing
such a capable video assistant.

Many endeavors have been made to incorporate video encoders with LLMs,
producing multimodal models capable of basic video understanding. Multimodal
models have found application in diverse tasks, illustrating their flexibility
and the breadth of their utility. These models have been successfully employed
in generating step-by-step instructions for complex tasks. This involves
understanding a text-based query and analyzing accompanying visual data to
produce a coherent, easily understandable sequence of instructions. A
multimodal model must have sufficient temporal understanding of events and
actions occurring within video inputs. Models should also be able to capture a
detailed understanding of the relationships among different actions presented
across a certain window of frames. Additionally, the reasoning ability to work
through the relationships between different tools, ingredients, or materials
is necessary for meaningful understanding of inputted tasks. This capability
represents a significant leap forward in models’ potential to assist with
practical, everyday tasks, offering personalized guidance that considers the
unique aspects of each scenario.

With the use of these models expanding across domains and into higher
complexity tasks, we wish to explore utilizing these models in domain-specific
step-by-step procedure understanding. We propose a specialized approach to
finetune and enhance the video summarization abilities of Large Vision
Language Models for step-by-step instruction generation across different
domains. Through the selected domains of cooking and medical procedure
summarization, we finetune multimodal language model TimeChat to (1) learn
instructional video explanations and event boundaries and (2) summarize the
primary procedural activities and their dependencies between clips concisely
(Ren2024, ). We specifically tune TimeChat on instruction data within the
recipe and medical video domain to generate succinct instructional
descriptions of health procedures and cooking steps. We additionally explore
transferring these learned skills between the recipe video and medical
procedural video domains.

Figure 1. Finetuned TimeChat on Cooking Domain Video Summarization

[fig:diagram]Finetuned TimeChat extracting recipe steps

##  2\. Related Work

###  2.1.  Multimodal Models (VLMS)

Advancements in integrating video and time-aware encoders into the
architectures of LLMs have given rise to models with multimodal capabilities.
Multimodality opens new opportunities for various forms of input and outputs,
such as video, audio, and timestamps. Large Vision Language Models (LVLMs)
merge computer vision and natural language processing techniques to construct
holistic comprehension and reasoning around visual, auditory, and textual
information. Many endeavors have been made to integrate video encoders with
LLMs for basic video question answering and detailed captioning (Jin2023, )
(Liu2023, ) (Song2023, ). Many of these methods focus primarily on general
video understanding skills like spatiotemporal reasoning and causal
relationship inference among simultaneous events. Video-ChatGPT is an LVLM
extension of the GPT architecture, leveraging LLaMA as its foundation
(Maaz2023, ). It employs CLIP ViT-L/14 as its visual encoder and Vicuna as its
large language model, the same encoder and decoders used in Video-LLaVA
(Radford2021, ). However, when testing Video-ChatGPT’s performance in recipe
generation, it does not accurately understand the steps and ingredients in the
provided cooking videos. The model exhibited poorer performance in summarizing
a health-related video that dealt with abstract and more technically prose-
heavy concepts and jargon. Despite these shortcomings, these model
architectures do show promise in utilizing their language abilities to
describe activities and scenarios. The natural language abilities of the LLMs
used in these models have the potential to compile and organize information
into meaningful and comprehensible instructions.

###  2.2. Domains

Video comprehension through multimodal models has been applied to several
domains and formats of videos. Many general comprehension datasets are
available to train models for general world knowledge of activities, fictional
plot understanding, first-person perspective actions, and so on (Lei2018, )
(Fan2019, ) (Li2020, ) (Yu2019, ) (Castro2020, ). More domain-specific multi-
modal datasets are being made available for tasks such as sports, traffic
conditions, and videogame gameplay analysis (Li2024, ) (Xu2021, ) (Mun2016, ).
The datasets for these models play a pivotal role in teaching models to detect
video highlights, generate dense captions, and summarize video and auditory
content.

Videos containing tutorials and procedures also provide key content for models
to learn from. Instructional videos can equip models with the skills to learn
detailed temporal relationships among events and materials. Long-format
tutorials specifically gauge the model’s abilities to synthesize detailed
explanations and lengthy procedures. They test the models’ skill at localizing
key events into concise timeframes and summarizing succinctly the description
of the event. Models can learn to synthesize content from demonstrations of
activities and human commentary. Cooking videos have been a challenging
instruction-tuning task for models. Multimodal models must learn the
relationship between ingredients and measurements used, as well as preparation
and recipe steps conducted to generate summaries from tutorials accurately.
Models should have an understanding of different food preparation techniques,
a vocabulary suitable for the cooking domain, and a temporal understanding of
boundaries between different steps.

Similar to cooking, the medical procedure domain also contains many video
tutorials for users. Thousands of medical procedure tutorials are posted to
YouTube by medical specialists and professionals for public use, both for
educational and healing purposes. Tutorials may include best safety practices,
proper equipment handling, expert recommendations, and correct techniques of
various treatments, procedures, and diagnoses. These videos range from in-
depth medical course material often viewed by medical students to simple
tutorials and explanations for non-professionals seeking at-home diagnoses and
remedies for their conditions. Both kinds of videos are excellent resources
for users but often are lengthy and require considerable effort to parse
through. Medical procedure videos resemble the structure of a recipe video,
with the placement of ingredients and materials required for the proposed
tutorial occurring before the demonstration of the main procedure at the
beginning of the videos. Both domains’ demonstrations center on presenting
viewers with slow play-by-play steps, narrating the exact description of each
action performed in depth.

###  2.3. Time-Sensitivity

Recently, time-sensitive encoders have led to improvements in modality fusion
and alignment. Before these integrations, existing Video LLMs (VLMs) could
only capture global visual semantics for short clips and failed to associate
the significant video content with accurate timestamps. For example, Video-
LLaMA and VideoChat struggle to localize and describe meaningful events in
untrimmed videos, leading to low accuracy. Additionally, the rigid compression
of converting video tokens to a fixed number does not scale well to longer
duration videos (Maaz2023, ) (Zhang2023a, ). Neglecting video duration in
these frameworks results in severe spatial-temporal semantics degradation when
processing massive frames from long videos. Timestamps are versatile in
utility, providing grounding and distinguishing relationships between moments.
Many techniques exist within pure computer vision models for highlight
detection and moment retrieval based utilizing timestamps and auditory
patterns present within videos (Lei2021, ) (Zala2023, ) (Zhang2023b, )
(Lin2023, ) (Yang2023, ). Time-aware encoders, as used in TimeChat, enhance
the binding of every frame’s visual context and timestamp descriptions
(Ren2024, ). TimeChat’s sliding video Q-Former accommodates adaptive video
token length during the extraction and compression of video features. The
sliding Q-Former compresses frames within a sliding window allowing dynamic
video token sequence generation of various lengths depending on video
duration. TimeChat’s ability to unify video tokens and timestamp information
allows for learning additional time-vision associations. This ability is
beneficial in the comprehension of lengthy but content-packed videos. More
information is encapsulated and is resistant to being left out during token
sampling. This is essential when building towards generating instruction
summaries, which require a significant amount of information to be parsed and
synthesized without dropping content with temporal ties throughout the video.
Additionally, timestamps are useful in grounding distinct temporal boundaries
between steps and localizing activities to precise windows within step
localization.

##  3\. Approach

Figure 2. Finetuning approach for Domain-Expert TimeChat

[fig:diagram]Finetuned TimeChat extracting recipe steps

###  3.1. Data Construction

Our approach entails finetuning TimeChat on a manually curated instruction-
tuning dataset comprised of instruction data to enhance the step localization
and video summarization abilities for cooking and medical procedural videos.
We finetune TimeChat on restructured versions of the Tasty cooking video
dataset for recipe understanding and the MedVidQA dataset published by TREC
for medical procedure understanding (Sener2019, ). The Tasty dataset consists
of 2511 recipe videos showcasing recipe procedures from an egocentric
perspective. Videos do not contain instruction narration and instead display
concise ingredient measurements and descriptions of steps at relevant frames.
Each recipe is annotated with the temporal boundaries for the steps within the
video. This dataset is apt for training the model for better step
localization, with the change of text descriptions typically serving as cues
to indicate boundaries between successive steps. The MedVidQA dataset consists
of 12,657 medical and health-related YouTube videos with narration of
procedures. The human narration alongside the videos provides the content to
synthesize into summaries. We split the Tasty and MedVidQA datasets into train
and test sets used during evaluation. The Tasty train set comprises 1757
videos, while the test set comprises 754 videos. The MedVidQA train set
consists of 8859 videos, while the test set contains 3798 videos.

These two video datasets are converted into an instruction-following format to
obtain high-quality video-centric instruction data. We follow the same process
utilized to construct the TimeIt dataset, comprising of an instruction writing
and answer formatting step (Ren2024, ). GPT-4 is used to extend manually
written instructions into diverse expressions. We reformulate the task outputs
into a user-friendly natural language response based on these written
expressions. For Tasty, the original JSON files containing step annotations
are restructured to include our manually written instruction queries with the
labeled original timestamps and steps.

Below is the annotation JSON format for a video from the Tasty dataset. Notice
that our reformulated task output and the original timestamp annotations
refactored together to form an instructional query and labeled response. Our
generated tasks generally task the model with identifying different activities
and breaking down the video into segments with timestamps based on the
temporal boundaries of completed activities. Descriptions should be concise
and clear in describing the main focus of the corresponding segment.

⬇

1{

2 "video": {"Tasty/clips/PrjXoDOpJ2Y_77_355.mp4"},

3 "QA": [

4 {"q": "Find, identify, and determine the temporal boundaries of a series of
distinct actions or steps occurring throughout the video. For each action,
output the corresponding start and end timestamps, accompanied by a concise
description.",

5 "a": "0.0 - 27.0 seconds, Add oil in pan. 27.0 - 67.0 seconds, Add chicken.
67.0 - 75.0 seconds, Mix sauces and garlic. 75.0 - 77.0 seconds, Add ginger
and sugar. 77.0 - 80.0 seconds, Add vinegar. 80.0 - 86.0 seconds, Add soy
sauce sesame oil. 86.0 - 90.0 seconds, Add water. 90.0 - 108.0 seconds, Mix it
all. 108.0 - 157.0 seconds, Saute the chicken. 157.0 - 160.0 seconds, Turn
heat on medium. 160.0 - 168.0 seconds, Add water chestnut. 168.0 - 186.0
seconds, Pour the sauce. 186.0 - 196.0 seconds, Cook it. 196.0 - 200.0
seconds, Turn heat off. 200.0 - 247.0 seconds, Put scallions. 247.0 - 278.0
seconds, Put in bowl."}

6 ]

7}

For the MedVidQA dataset, we construct video annotations manually through
crowdsourcing, similar to methods followed by TVSum (Song2015, ). We utilized
the Prolific platform to publish annotation requirements and collect annotator
responses. Two responses were collected per video. Participants were asked to
(1) watch the entire duration of the video (2) provide an importance score of
1 (not important) to 5 (very important) to each of uniform length (2 seconds)
shots for the whole video. Like Tasty, these generated step annotations are
restructured to include our manually written instruction queries.

Below is an example from our constructed annotation JSON file for a video from
the MedVidQA dataset. The saliency scores were collected from human annotators
and normalized.

⬇

1{

2 "video": {"MedVidQA/videos/takeblood.mp4"},

3 "QA": [

4 {"q": "Transcribed speech: None. Based on the video content and possible
transcribed speech, You are given a video from the MedVidQA dataset. Please
find the highlight contents in the video, determining the highlight timestamps
and its saliency score on a scale from 1 to 5. The output format should be
like: ’The highlight timestamps are in the 82, 84, 86, 88, 90, 92, 94, 96, 98,
100 second. Their saliency scores are 1.3, 1.7, 1.7, 1.7, 1.7, 1.3, 1.7, 2.3,
2.3, 2.3’.",

5 "a": "The highlight timestamps are in the 17.0, 20.5, 37.5, 39.5, 56.5,
64.0, 73.5 seconds. Their saliency scores are 2.2, 2.2, 2.2, 3.4, 3.1, 1.9,
2.6."}

6 ]

7}

###  3.2. Implementation Details

ViT-G/14 from EVA-CLIP is used as the image encoder, and LLaMA-2 (7B) is used
as the foundation language model (Sun2023, ) (Touvron2023, ). The parameters
for the image Q-Former are initialized from InstructBLIP’s checkpoint, while
the video Q-Former is initialized from Video-LLaMA’s checkpoint. TimeChat is
finetuned on our constructed instruction tuning dataset for 3 epochs using a
32 batch size with a single NVIDIA 8-V100 (32GB) GPU through LORA PEFT
finetuning. All other hyperparameters and frame-level configurations follow
TimeChat’s initialization.

##  4\. Results

###  4.1. Evaluation Setup

We evaluate our model on the tasks of video summarization and step
localization. We split the Tasty and MedVidQA datasets into train and test
sets to construct some benchmarks on which to evaluate our model. The Tasty
test set contains 754 videos, while the MedVidQA test set contains 3798
videos. We additionally constructed a video summarization generation dataset
utilizing YouCook2 (Zhou2017, ). By default, the dataset consists of 2000 long
untrimmed videos from 89 cooking recipes; each distinct recipe has 22 videos
on average. The procedure steps for each video are annotated with temporal
boundaries and are described by imperative sentences. The videos were
downloaded from YouTube and are all in the third-person viewpoint. All the
videos are unconstrained and can be performed by individuals at their houses
with unfixed cameras. We parsed through the associated recipes from each video
to create a dataset of questions asking for summaries for each recipe
procedure. Our final dataset contained 408 videos from 62 different cooking
recipes. The MedVidQA and YouCook2 datasets evaluate video summarization
abilities across tested models, while Tasty is used in evaluating step
localization. Hence, for MedVidQA and YouCook2, we report the maP and
f1-scores per video. For Tasty, we report the maP score. We compare our model
to TimeChat before finetuning, Video-LLaMA, and Valley. All compared models
are considered end-to-end models, directly taking in videos as inputs and
generating text outputs in an end-to-end matter.

###  4.2. Results Analysis

To expand further on our findings from finetuning TimeChat for domain-specific
video summarization and step localization enhancement, we delve deeper into
the specific outcomes observed through our experiments. Our investigation
centered on comparing the quality of generated procedural video summarizations
and step understanding of baseline TimeChat and TimeChat finetuned on the
video domains of recipes and medical procedures. Our experimental results
demonstrate that our method of finetuning TimeChat leads to some boosts in
generating precise video summarizations and distinguishing successive steps
from one another over general-purpose trained TimeChat. This improvement is
quantitatively evident when examining the f1 score comparisons of finetuned
TimeChat (FT-TimeChat) and baseline TimeChat on the constructed YouCook2
datasets in Table 1. The model subjected to finetuning performed with a
slightly higher f-1 score than baseline TimeChat as well as Video-LLaMA and
Valley. See Table 1 for Video Summarization comparisons across evaluated
models.

Model | YouCook2 | MedVidQA
---|---|---
| f1 | maP | f1 | maP
Video-LLaMA | 2.6 | 11.3 | 1.4 | 8.7
Valley | 1.9 | 10.9 | 1.2 | 7.4
TimeChat | 12.4 | 17.6 | 6.9 | 14.5
FT-TimeChat | 12.7 | 16.8 | 7.3 | 13.7
Table 1. Performance of end-to-end models on video summarization of videos
from YouCook2 and MedVidQA.

Table 2 compares step localization across each model on the Tasty test
dataset. Mean average precision (maP) was the only metric tracked in
evaluating step localization.

Model | Tasty
---|---
| maP
Video-LLaMA | 15.6
Valley | 15.2
TimeChat | 17.7
FT-TimeChat | 18.1
Table 2. Performance of end-to-end models on step localization of videos from
Tasty.

Despite finetuning on a larger corpus of medical-related videos than cooking
videos given our train and test set sizes mentioned earlier, f1 scores and
mean average precision scores on YouCook2 and MedVidQA seem to indicate that
the model performed better on video summarization within the cooking procedure
domain. When evaluating step localization abilities on the Tasty dataset,
fine-tuned TimeChat slightly outperforms the baseline version in separating
out steps within recipes.

Figure 3. Finetuned TimeChat on Medical Domain Video Summarization

[fig:diagram]Finetuned TimeChat extracting recipe steps

One observation we made that could explain this finding was that baseline
TimeChat tended to mistake body parts showcased in the video during a
demonstration. Before finetuning, TimeChat frequently mistook an arm for a leg
in a video demonstrating how to draw blood from patients. Certain medical
equipment and materials like tourniquets and gauze were often mislabeled in
summaries due to such terminology not being included in the model’s
vocabulary. Finetuning expanded TimeChat’s vocabulary subject to the domain,
helping produce more precise and descriptive summaries. Finetuned TimeChat
also tended to produce more concise recipe steps than baseline TimeChat, whose
responses were often more lengthy.

There is room for more robust evaluation through employing human evaluation on
a subset of responses from finetuned TimeChat and baseline TimeChat. We can
gather a group of people to blindly judge between the summaries generated by
both models which response is more accurate to a provided ground truth for a
subset of responses produced by both models. Additionally, we can also break
down the evaluation into 2 stages: (1) where annotators can check if generated
segments line up change of events or change of activities within the video and
(2) annotators can check if the generated description aligns with the activity
occurring during the segment.

##  5\. Conclusion and Future Work

###  5.1. Conclusion

In conclusion, this research underscores the potential of leveraging
Multimodal Large Language Models to enhance the comprehension and
summarization of instructional videos with the cooking and medical doamins. By
fine-tuning TimeChat on domain-specific datasets like Tasty and MedVidQA, we
have demonstrated the model’s improved ability to localize key events and
generate concise, accurate summaries of step-by-step procedures in cooking and
medical tutorials. The restructuring of domain-specific datasets into an
instruction-following format, combined with the use of GPT-4 for expanding
instruction diversity, has facilitated the creation of high-quality video-
centric instruction data. This data is crucial for training models to handle a
variety of instructional queries accurately and effectively. The enhanced
capabilities of TimeChat in understanding and summarizing video content hold
significant promise for practical applications. From providing detailed
cooking instructions to summarizing complex medical procedures, the model can
offer personalized, step-by-step guidance tailored to the unique aspects of
each scenario.

###  5.2. Future Work

One avenue of further investigation is training the frame encoder to segment
videos into non-continuous time frames. Currently, generated segments occur
continuously with the time frames of successive steps often having start times
that line up immediately after the end time of prior steps. While this is
useful for sectioning of a video into chunks based on steps or activities, it
is also useful to generate tight segments that are confined to the key
highlights. Currently, segments can be edited down to tighter time frames that
encapsulate content aligned with the exact descriptions generated by the
model. If each generated segment were to be combined into a new video, the
video should only contain the video highlights.

Another area worth exploring is the use of medical procedure data from other
modalities to finetune the model on more domain-specific information. There
was a significant amount of data from various datasets available within the
cooking domain that could be used in this experiment for finetuning the model.
Within the medical procedure domain, we were limited to MedVidQA to provide
videos that could be used in both training and evaluation. One possibility to
add more medical data could be generating instruction data from health
articles that provide tutorials and at-home procedures. Many at-home remedies
and healthy-related articles with images demonstrating procedures exist online
on websites like MayoClinic, MedlinePlus, and WikiHow. Through careful
processing of required materials, procedural steps, and recommendations, we
can construct additional datasets that can expose the model to a larger corpus
of medical terminology and practices useful in growing the model’s reasoning
within the medical domain.

From a development perspective, we hope to containerize our current workflow
that runs on a 32GB 8-V100 GPU cluster hosted on an AWS Lambda instance. This
server instance has been quite useful throughout this project but has also
incurred quite the cost. We wish to create a Docker image of our development
environment to simplify the infrastructure setup process for different server
architectures. We also hope to look into more fine-grained batch processing at
the fine-tuning stage to speed up the process. Additionally, we hope to build
a user interface with Gradio to accommodate the display of the generated
segment summarizations, along with their corresponding video frame groundings.
Presenting users with an edited down version of the video from the segments
along with the segment descriptions as captions to accompany the video would
be useful in application of this type of model.

## References

  * (1) Ren, S., Yao, L., Li, S., Sun, X., & Hou, L. (2023). TimeChat: A Time-sensitive Multimodal Large Language Model for Long Video Understanding. ArXiv, abs/2312.02051.
  * (2) Jin, P., Takanobu, R., Zhang, C., Cao, X., & Yuan, L. (2023). Chat-UniVi: Unified Visual Representation Empowers Large Language Models with Image and Video Understanding. ArXiv, abs/2311.08046.
  * (3) Liu, H., Fan, Q., Liu, T., Yang, L., Tao, Y., Huang, H., He, R., & Yang, H. (2023). Video-Teller: Enhancing Cross-Modal Generation with Fusion and Decoupling. ArXiv, abs/2310.04991.
  * (4) Song, E., Chai, W., Wang, G., Zhang, Y., Zhou, H., Wu, F., Guo, X., Ye, T., Lu, Y., Hwang, J., & Wang, G. (2023). MovieChat: From Dense Token to Sparse Memory for Long Video Understanding. ArXiv, abs/2307.16449.
  * (5) Fan, C. (2019). EgoVQA - An Egocentric Video Question Answering Benchmark Dataset. 2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW), 4359-4366.
  * (6) Lin, B., Zhu, B., Ye, Y., Ning, M., Jin, P., & Yuan, L. (2023). ”Video-LLaVA: Learning United Visual Representation by Alignment Before Projection.” ArXiv, abs/2311.10122.
  * (7) Lei, J., Yu, L., Bansal, M., & Berg, T.L. (2018). TVQA: Localized, Compositional Video Question Answering. Conference on Empirical Methods in Natural Language Processing.
  * (8) Li, L., Chen, Y., Cheng, Y., Gan, Z., Yu, L., & Liu, J. (2020). Hero: Hierarchical Encoder for Video+Language Omni-representation Pre-training. Conference on Empirical Methods in Natural Language Processing.
  * (9) Yu, Z., Xu, D., Yu, J., Yu, T., Zhao, Z., Zhuang, Y., & Tao, D. (2019). ActivityNet-QA: A Dataset for Understanding Complex Web Videos via Question Answering. ArXiv, abs/1906.02467.
  * (10) Castro, S., Azab, M., Stroud, J.C., Noujaim, C., Wang, R., Deng, J., & Mihalcea, R. (2020). LifeQA: A Real-life Dataset for Video Question Answering. International Conference on Language Resources and Evaluation.
  * (11) Mun, J., Seo, P.H., Jung, I., & Han, B. (2016). MarioQA: Answering Questions by Watching Gameplay Videos. 2017 IEEE International Conference on Computer Vision (ICCV), 2886-2894.
  * (12) Li, H., Deng, A., Ke, Q., Liu, J., Rahmani, H., Guo, Y., Schiele, B., & Chen, C. (2024). Sports-QA: A Large-Scale Video Question Answering Benchmark for Complex and Professional Sports. ArXiv, abs/2401.01505.
  * (13) Xu, L., Huang, H., & Liu, J. (2021). SUTD-TrafficQA: A Question Answering Benchmark and an Efficient Network for Video Reasoning over Traffic Events. 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 9873-9883.
  * (14) Zhang, H., Li, X., & Bing, L. (2023). Video-LLaMA: An Instruction-tuned Audio-Visual Language Model for Video Understanding. ArXiv, abs/2306.02858.
  * (15) Maaz, M., Rasheed, H.A., Khan, S., & Khan, F.S. (2023). Video-ChatGPT: Towards Detailed Video Understanding via Large Vision and Language Models. ArXiv, abs/2306.05424.
  * (16) Li, K., He, Y., Wang, Y., Li, Y., Wang, W., Luo, P., Wang, Y., Wang, L., & Qiao, Y. (2023). VideoChat: Chat-Centric Video Understanding. ArXiv, abs/2305.06355.
  * (17) Radford, A., Kim, J.W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., & Sutskever, I. (2021). Learning Transferable Visual Models From Natural Language Supervision. International Conference on Machine Learning.
  * (18) Zhou, L., & Corso, J.J. (2017). YouCookII Dataset.
  * (19) Sener, F., & Yao, A. (2018). Zero-Shot Anticipation for Instructional Activities. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), 862-871.
  * (20) Lei, J., Berg, T.L., & Bansal, M. (2021). QVHighlights: Detecting Moments and Highlights in Videos via Natural Language Queries. ArXiv, abs/2107.09609.
  * (21) Zala, A., Cho, J., Kottur, S., Chen, X., Ouguz, B., Mehdad, Y., & Bansal, M. (2023). Hierarchical Video-Moment Retrieval and Step-Captioning. 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 23056-23065.
  * (22) Zhang, K., Chao, W., Sha, F., & Grauman, K. (2016). Video Summarization with Long Short-Term Memory. ArXiv, abs/1605.08110.
  * (23) Yang, A., Nagrani, A., Seo, P.H., Miech, A., Pont-Tuset, J., Laptev, I., Sivic, J., & Schmid, C. (2023). Vid2Seq: Large-Scale Pretraining of a Visual Language Model for Dense Video Captioning. 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 10714-10726.
  * (24) Song, Y., Vallmitjana, J., Stent, A., & Jaimes, A. (2015). TVSum: Summarizing web videos using titles. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 5179-5187.
  * (25) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., & Lample, G. (2023). LLaMA: Open and Efficient Foundation Language Models. ArXiv, abs/2302.13971.
  * (26) Sun, Q., Fang, Y., Wu, L.Y., Wang, X., & Cao, Y. (2023). EVA-CLIP: Improved Training Techniques for CLIP at Scale. ArXiv, abs/2303.15389.


# On the problem of Pillai with $k$–generalized
Fibonacci numbers and powers of $3$

Mahadi Ddamulira<EMAIL_ADDRESS><EMAIL_ADDRESS>Institute of
Analysis and Number Theory
Graz University of Technology
Kopernikusgasse 24/II
A- 8010 Graz, Austria
Florian Luca  School of Mathematics
University of the Witwatersrand
Private Bag X3, WITS 2050
Johannesberg, South Africa  Research Group in Algebraic Structures and
Applications
King Abdulaziz University
Jeddah, Saudi Arabia<EMAIL_ADDRESS>Centro de Ciencias Matemáticas,
UNAM
Morelia, Michoacán, México

(22 Mayy 2019; 3 March 2020; 3 March 2020)

###### Abstract

For an integer $k\geq 2$, let $\\{F^{(k)}_{n}\\}_{n\geq 2-k}$ be the
$k$–generalized Fibonacci sequence which starts with $0,\ldots,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.

Published 9 April 2020

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

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.

##  1 Introduction

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

$\displaystyle a^{x}-b^{y}=c,~{}~{}~{}~{}~{}\min\\{x,y\\}\geq 2,$ (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 [21]. In 1936 (see [22, 23]), in the special case
$(a,b)=(3,2)$ which is a continutation of the work of Herschfeld [18, 19] in
1935, Pillai conjectured that the only integers $c$ admitting at least two
representations of the form $2^{x}-3^{y}$ are given by

$\displaystyle
2^{3}-3^{2}=2^{1}-3^{1}=-1,~{}~{}~{}2^{5}-3^{3}=2^{3}-3^{1}=5,~{}~{}~{}2^{8}-3^{5}=2^{4}-3^{1}=13.$
(2)

This was confirmed by Stroeker and Tijdeman [24] 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. See, for example, [4, 7, 8, 9, 10, 11,
15, 16].

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

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

with the initial conditions

$F_{-(k-2)}^{(k)}=F_{-(k-3)}^{(k)}=\cdots=F_{0}^{(k)}=0\quad{\text{\rm 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,\ldots,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{\rm holds for all}}\quad 2\leq n\leq k+1.$ (4)

We also observe that the recursion (3) implies the three–term recursion

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

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

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

$\displaystyle F_{n}^{(k)}-F_{m}^{(\ell)}=c$ (5)

has at least two solutions $(n,m)$. We are not aware of a general treatment of
equation (5) (namely, considering $k$ and $\ell$ parameters), although the
particular case when $\\{k,\ell\\}=\\{2,3\\}$ was treated in [7].

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

$\displaystyle F_{n}^{(k)}-2^{m}=c,$ (6)

where $k$ is also a parameter, which is a variation of equation (5). They
determined all integers $c$ such that equation (6) has at least two solutions
$(n,m)$. These $c$ together with their multiple representations as in (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

$\displaystyle F_{n}^{(k)}-3^{m}=F_{n_{1}}^{(k)}-3^{m_{1}}~{}~{}~{}~{}(=c)$
(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 [9] and [10], respectively. So, we focus on
the case $k\geqslant 4$.

######  Theorem 1.1.

For fixed integer $k\geq 4$, the Diophantine equation (7) with $n>n_{1}\geq 2$
and $m>m_{1}\geq 1$ has:

  * (i)

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

$\displaystyle F_{5}^{(k)}-3^{2}$ $\displaystyle=$ $\displaystyle
F_{3}^{(k)}-3^{1}~{}~{}=~{}-1,~{}~{}~{}k\geq 4,$ $\displaystyle
F_{7}^{(k)}-3^{3}$ $\displaystyle=$ $\displaystyle
F_{5}^{(k)}-3^{1}~{}~{}=~{}~{}5,~{}~{}~{}k\geq 6,$ $\displaystyle
F_{10}^{(k)}-3^{5}$ $\displaystyle=$ $\displaystyle
F_{6}^{(k)}-3^{1}~{}~{}=~{}~{}13,~{}~{}~{}k\geq 9;$

  * (ii)

solutions with $c\in\\{-25,-7,5\\}$ and $n\geq k+2$ and $k\in\\{4,5,6\\}$.
Futhermore, all the representations of $c$ in this case are given by

$\displaystyle F_{8}^{(4)}-3^{4}$ $\displaystyle=$ $\displaystyle
F_{3}^{(4)}-3^{3}~{}~{}=~{}-25,$ $\displaystyle F_{10}^{(5)}-3^{5}$
$\displaystyle=$ $\displaystyle F_{3}^{(5)}-3^{2}~{}~{}=~{}-7,$ $\displaystyle
F_{10}^{(6)}-3^{5}$ $\displaystyle=$ $\displaystyle
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 algebra 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_{0}x^{d}+a_{1}x^{d-1}+\cdots+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):=\dfrac{1}{d}\left(\log
a_{0}+\sum_{i=1}^{d}\log\left(\max\\{|\eta^{(i)}|,1\\}\right)\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:

$\displaystyle h(\eta\pm\gamma)$ $\displaystyle\leq$ $\displaystyle
h(\eta)+h(\gamma)+\log 2,$ $\displaystyle h(\eta\gamma^{\pm 1})$
$\displaystyle\leq$ $\displaystyle h(\eta)+h(\gamma),$ (8) $\displaystyle
h(\eta^{s})$ $\displaystyle=$ $\displaystyle|s|h(\eta)\qquad(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\geq 2-k}$, namely

$\Psi_{k}(x):=x^{k}-x^{k-1}-\cdots-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\left(1-2^{-k}\right)$ and $2$ (see [13]). 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)},\dotso,\alpha^{(k)}$ for all roots of $\Psi_{k}(x)$ with the
convention that $\alpha^{(1)}:=\alpha$.

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

$\displaystyle f_{k}(z)=\dfrac{z-1}{2+(k+1)(z-2)}\qquad{\text{for}}\qquad
z\in\mathbb{C}.$ (9)

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

$\displaystyle
F_{m}^{(k)}=\sum_{i=1}^{k}f_{k}(\alpha^{(i)}){\alpha^{(i)}}^{m-1}.$ (10)

It was proved in [13] that the contribution of the roots which are inside the
unit circle to the formula (10) is very small, namely that the approximation

$\left|F_{m}^{(k)}-f_{k}(\alpha)\alpha^{m-1}\right|<\dfrac{1}{2}\quad\mbox{holds~{}
for~{} all~{} }m\geqslant 2-k.$ (11)

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

$\displaystyle\alpha^{m-2}\leq F_{m}^{(k)}\leq\alpha^{m-1}\qquad{\text{\rm
holds for all}}\qquad m\geq 1\quad{\text{\rm and}}\quad k\geq 2.$ (12)

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\geq 2$, $\alpha$ be the dominant root of $\\{F^{(k)}_{m}\\}_{m\geq
2-k}$, and consider the function $f_{k}(z)$ defined in (9).

  * (i)

The inequalities

$\dfrac{1}{2}<f_{k}(\alpha)<\dfrac{3}{4}\qquad\text{and}\qquad|f_{k}(\alpha^{(i)})|<1,\qquad
2\leq i\leq 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 use the following result by Matveev [20], which is one of our
main tools in this paper.

######  Theorem 2.2 (Matveev).

Let $\gamma_{1},\ldots,\gamma_{t}$ be positive real algebraic numbers in a
real algebraic number field $\mathbb{K}$ of degree $D$, $b_{1},\ldots,b_{t}$
be nonzero integers, and assume that

$\Lambda:=\gamma_{1}^{b_{1}}\cdots\gamma_{t}^{b_{t}}-1$ (13)

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\geq\max\\{|b_{1}|,\ldots,|b_{t}|\\},$

and

$A_{i}\geq\max\\{Dh(\gamma_{i}),|\log\gamma_{i}|,0.16\\},\qquad{\text{for
all}}\qquad i=1,\ldots,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 [14], 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$. Let further $\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\leq M\quad{\text{and}}\quad w\geq\dfrac{\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.

######  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}}.$ (14)

Then $x/y=p_{k}/q_{k}$ is a convergent of $\tau$. Furthermore,

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

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

######  Lemma 2.5 (Gúzman, Luca).

If $m\geqslant 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)\neq(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}\\}\geq 2$, we get that $n=n_{1}$. Thus, $(n,m)=(n_{1},m_{1})$,
contradicting our assumption. Hence, $m\neq m_{1}$, and we may assume without
loss of generality that $m>m_{1}\geq 1$. Since

$\displaystyle F_{n}^{(k)}-F_{n_{1}}^{(k)}$ $\displaystyle=$ $\displaystyle
3^{m}-3^{m_{1}},$ (16)

and the right–hand side of (16) is positive, we get that the left–hand side of
(16) is also positive and so $n>n_{1}$. Furthermore, since
$F_{1}^{(k)}=F_{2}^{(k)}=1$, we may assume that $n>n_{1}\geq 2$.

We analyse the possible situations.

Case 1. Assume that $2\leq n_{1}<n\leq k+1$. Then, by (4), we have

$\displaystyle F_{n_{1}}^{(k)}=2^{n_{1}-2}\qquad{\rm and}\qquad
F_{n}^{(k)}=2^{n-2}$

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

$\displaystyle 2^{n-2}-3^{m}=2^{n_{1}-2}-3^{m_{1}}.$

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

$\displaystyle F_{5}^{(k)}-3^{2}$ $\displaystyle=$ $\displaystyle
F_{3}^{(k)}-3^{1}~{}~{}=~{}-1,~{}~{}~{}k\geq 4,$ $\displaystyle
F_{7}^{(k)}-3^{3}$ $\displaystyle=$ $\displaystyle
F_{5}^{(k)}-3^{2}~{}~{}=~{}~{}5,~{}~{}~{}k\geq 6,$ (17) $\displaystyle
F_{10}^{(k)}-3^{5}$ $\displaystyle=$ $\displaystyle
F_{6}^{(k)}-3^{1}~{}~{}=~{}~{}13,~{}~{}~{}k\geq 9.$

Case 2. Assume $n\geq k+2$. The following lemma is useful.

######  Lemma 3.1.

For $n\geq 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 3.2.

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\geq 2}$ is $0$ at
$n=2,3,\ldots,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{\rm holds~{}for}}\quad
n\geq k+2.$

This is equivalent to

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

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

$\sum_{i=n-k+1}^{n-1}F_{i}\leq\sum_{i=n-k+1}^{n-1}2^{i-2}<1+2+\cdots+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\geq k+2$. Thus,
$2^{n-2}-3^{m}\neq 2^{n_{1}-2}-3^{m_{1}}$. Since $n>n_{1}\geq 2$, we have that
$F_{n_{1}}^{(k)}\leq F_{n-1}^{(k)}$ and therefore

$F_{n}^{(k)}=F_{n-1}^{(k)}+\cdots+F_{n-k}^{(k)}\geq
F_{n-1}^{(k)}+\cdots+F_{n-k-1}^{(k)}\geq
F_{n_{1}}^{(k)}+\cdots+F_{n-k-1}^{(k)}.$

So, from the above, (12) and (16), we have

$\displaystyle\alpha^{n-4}$ $\displaystyle\leq$ $\displaystyle
F_{n-2}^{(k)}\leq F_{n}^{(k)}-F_{n_{1}}^{(k)}=3^{m}-3^{m_{1}}<3^{m},\text{ and
}$ (18) $\displaystyle\alpha^{n-1}$ $\displaystyle\geq$ $\displaystyle
F_{n}^{(k)}>F_{n}^{(k)}-F_{n_{1}}^{(k)}=3^{m}-3^{m_{1}}\geq 3^{m-1},$

leading to

$\displaystyle 1+\left(\dfrac{\log
3}{\log\alpha}\right)(m-1)<n<\left(\dfrac{\log 3}{\log\alpha}\right)m+4.$ (19)

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

$\displaystyle\left|f_{k}(\alpha)\alpha^{n-1}-3^{m}\right|$ $\displaystyle=$
$\displaystyle\left|(f_{k}(\alpha)\alpha^{n-1}-F_{n}^{(k)})+(F_{n_{1}}^{(k)}-3^{m_{1}})\right|$
$\displaystyle=$
$\displaystyle\left|(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}})\right|$
$\displaystyle<$
$\displaystyle\dfrac{1}{2}+\dfrac{1}{2}+\alpha^{n_{1}-1}+3^{m_{1}}$
$\displaystyle<$ $\displaystyle\alpha^{n_{1}}+3^{m_{1}}$ $\displaystyle<$
$\displaystyle 2\max\\{\alpha^{n_{1}},3^{m_{1}}\\}.$

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

$\displaystyle\left|f_{k}(\alpha)\alpha^{n-1}3^{-m}-1\right|<2\max\left\\{\dfrac{\alpha^{n_{1}}}{3^{m}},3^{m_{1}-m}\right\\}<\max\\{\alpha^{n_{1}-n+6},3^{m_{1}-m+1}\\},$
(20)

where for the right–most inequality in (20) we used (18) and the fact that
$\alpha^{2}>2$.

For the left-hand side of (20) above, 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
$\mathbb{K}:=\mathbb{Q}(\alpha)$, so we can take
$D:=[\mathbb{K}:\mathbb{Q}]=k$. Put

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

To see why $\Lambda\neq 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 (20) 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 (20), 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 1. $\min\\{(n-n_{1})\log\alpha,(m-m_{1})\log 2\\}=(n-n_{1})\log\alpha$.

In this case, we rewrite (16) as

$\displaystyle\left|f_{k}(\alpha)\alpha^{n-1}-f_{k}(\alpha)\alpha^{n_{1}-1}-3^{m}\right|$
$\displaystyle=$
$\displaystyle\left|(f_{k}(\alpha)\alpha^{n-1}-F_{n}^{(k)})+(F_{n_{1}}^{(k)}-f_{k}(\alpha)\alpha^{n_{1}-1})-3^{m_{1}}\right|$
$\displaystyle<$ $\displaystyle\dfrac{1}{2}+\dfrac{1}{2}+3^{m_{1}}\leq
3^{m_{1}+1}.$

Dividing through by $3^{m}$ gives

$\displaystyle\left|f_{k}(\alpha)(\alpha^{n-n_{1}}-1)\alpha^{n_{1}-1}3^{-m}-1\right|$
$\displaystyle<$ $\displaystyle 3^{m_{1}-m+1}.$ (21)

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,\quad
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\geq 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}}|\geq 3$.

Since

$h(\gamma_{1})\leq h(f_{k}(\alpha))+h(\alpha^{n-n_{1}}-1)<3\log
k+(n-n_{1})\dfrac{\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(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 (21), we get that

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

Case 2. $\min\\{(n-n_{1})\log\alpha,(m-m_{1})\log 3\\}=(m-m_{1})\log 3$.

In this case, we write (16) as

$\displaystyle\left|f_{k}(\alpha)\alpha^{n-1}-3^{m}+3^{m_{1}}\right|$
$\displaystyle=$
$\displaystyle\left|(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}\right|$
$\displaystyle<$
$\displaystyle\dfrac{1}{2}+\dfrac{1}{2}+\alpha^{n_{1}-1}~{}~{}<~{}~{}\alpha^{n_{1}},$

so that

$\displaystyle\left|f_{k}(\alpha)(3^{m-m_{1}}-1)^{-1}\alpha^{n-1}3^{-m_{1}}-1\right|<\dfrac{\alpha^{n_{1}}}{3^{m}-3^{m_{1}}}\leq\dfrac{2\alpha^{n_{1}}}{3^{m}}<\alpha^{n_{1}-n+6}.$
(22)

The above inequality (22) 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,\quad
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})\leq h(f_{k}(\alpha))+h(3^{m-m_{1}}-1)<3\log
k+(m-m_{1}+k)\dfrac{\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 (22), 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 Case $1$ and Case $2$, we have

$\displaystyle\min\\{(n-n_{1})\log\alpha,(m-m_{1})\log 2\\}$ $\displaystyle<$
$\displaystyle 6.6\times 10^{11}k^{4}\log^{2}k(1+\log n),$ (23)
$\displaystyle\max\\{(n-n_{1})\log\alpha,(m-m_{1})\log 2\\}$ $\displaystyle<$
$\displaystyle 7.5\times 10^{22}k^{7}\log^{3}k(1+\log n)^{2}.$

We now finally rewrite equation (16) as

$\left|f_{k}(\alpha)\alpha^{n-1}-f_{k}(\alpha)\alpha^{n_{1}-1}-3^{m}+3^{m_{1}}\right|=\left|(f_{k}(\alpha)\alpha^{n-1}-F_{n}^{(k)})+(F_{n_{1}}^{(k)}-f_{k}(\alpha)\alpha^{n_{1}-1})\right|<1.$

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

$\displaystyle\left|\dfrac{f_{k}(\alpha)(\alpha^{n-n_{1}}-1)}{3^{m-m_{1}}-1}\alpha^{n_{1}-1}3^{-m_{1}}-1\right|<\dfrac{1}{3^{m}-3^{m_{1}}}\leq\dfrac{2}{3^{m}}<3^{5-0.8n},$
(24)

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

$t:=3,\quad\gamma_{1}:=\dfrac{f_{k}(\alpha)(\alpha^{n-n_{1}}-1)}{3^{m-m_{1}}-1},\quad\gamma_{2}:=\alpha,\quad\gamma_{3}:=3,\quad
b_{1}:=1,\quad b_{2}:=n_{1}-1,\quad b_{3}:=-m_{1}.$

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

$\displaystyle kh(\gamma_{1})$ $\displaystyle\leq$ $\displaystyle
k\left(h(f_{k}(\alpha))+h(\alpha^{n-n_{1}}-1)+h(3^{m-m_{1}}-1)\right)$
$\displaystyle<$ $\displaystyle 3k\log k+(n-n_{1})\log\alpha+k(m-m_{1})\log
3+2k\log 2$ $\displaystyle<$ $\displaystyle 8.3\times
10^{22}k^{8}\log^{3}k(1+\log n)^{2},$

where in the above chain of inequalities we used the bounds (23). 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}:=\dfrac{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\geq 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|\geq 4$.
Thus, $\Lambda_{3}\neq 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)\left(8.3\times 10^{22}\log^{3}k(1+\log n)^{2}\right)(\log 2)(\log 3),$

which together with (24) 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

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

which can be equivalently written as

$\displaystyle\dfrac{n}{(\log n)^{3}}$ $\displaystyle<$ $\displaystyle
6.2\times 10^{34}k^{11}\log^{4}k.$ (25)

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

$\displaystyle n$ $\displaystyle<$ $\displaystyle 8\times(6.2\times
10^{34}k^{11}\log^{4}k)\log(6.2\times 10^{34}k^{11}\log^{4}k)^{3}$ (26)
$\displaystyle<$ $\displaystyle 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 equation (7)
with $(n,m)\neq(n_{1},m_{1})$, $n>\min\\{k+2,n_{1}+1\\}$, $n_{1}\geq 2$,
$m>m_{1}\geq 1$ and $k\geq 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

$\displaystyle 4\times 10^{42}k^{11}(\log k)^{7}$ $\displaystyle<$
$\displaystyle 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 equation (16)
which is equivalent to (7). For $k\in[4,600]$ and $n\in[3,600]$, consider the
sets

$\displaystyle
F_{n,k}:=\left\\{F_{n}^{(k)}-F_{n_{1}}^{(k)}(\text{mod}~{}10^{20}):~{}n\in[3,600],~{}n_{1}\in[2,n-1]\right\\}$

and

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

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 (20) and put

$\displaystyle\Gamma:=(n-1)\log\alpha-m\log 3+\log(f_{k}(\alpha)).$ (27)

For technical reasons we assume that $\min\\{n-n_{1},m-m_{1}\\}\geq 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}\geq 20$, we consider (21);

  * (ii)

if $n-n_{1}\geq 20$ but $m-m_{1}<20$, we consider (22);

  * (iii)

if $n-n_{1}<20$ but $m-m_{1}<20$, we consider (24).

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

$\displaystyle
0<\Gamma<e^{\Gamma}-1<\max\left\\{\alpha^{n_{1}-n+6},3^{m_{1}-m+1}\right\\}.$

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

$\displaystyle 0<|\Gamma|\leq
e^{|\Gamma|}-1=e^{|\Gamma|}|e^{\Gamma}-1|<2\max\left\\{\alpha^{n_{1}-n+6},3^{m_{1}-m+1}\right\\}.$

Therefeore, in any case, the following inequality holds

$\displaystyle
0<|\Gamma|<2\max\left\\{\alpha^{n_{1}-n+6},3^{m_{1}-m+1}\right\\}.$ (28)

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

$\displaystyle 0<\left|(n-1)\left(\dfrac{\log\alpha}{\log
3}\right)-m+\dfrac{\log(f_{k}(\alpha))}{\log
3}\right|<\max\left\\{(2\alpha^{6})\cdot\alpha^{-(n-n_{1})},\dfrac{6}{\log
3}\cdot 3^{-(m-m_{1})}\right\\}$

Then, we apply Lemma 2.3 with the following data

$\displaystyle k\in[4,600],~{}~{}~{}~{}\tau_{k}:=\dfrac{\log\alpha}{\log
3},~{}~{}~{}~{}\mu_{k}:=\dfrac{\log(f_{k}(\alpha))}{\log
3},~{}~{}~{}~{}(A_{k},B_{k}):=(2\alpha^{6},\alpha)\text{ or
}\left(\dfrac{6}{\log 3},3\right).$

Next, we put $M_{k}:=\lfloor 4\times 10^{42}k^{11}(\log k)^{7}\rfloor$, 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^{6}q/\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

$\displaystyle
n-n_{1}<\dfrac{\log(2\alpha^{6}q/\varepsilon)}{\log\alpha}<600,~{}~{}~{}\text{
or }m-m_{1}<\dfrac{\log((6/\log 3)q/\varepsilon)}{\log 3}<375.$

Therefore, we have that either $n-n_{1}\leq 600$ or $m-m_{1}\leq 375$.

Now, let us assume that $n-n_{1}\leq 600$. In this case, we consider the
inequality (21) and assume that $m-m_{1}\geq 20$. Then we put

$\displaystyle\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 (28), from (21) we
get

$\displaystyle 0<|\Gamma_{1}|<\dfrac{6}{3^{m-m_{1}}},$

and replacing $\Gamma_{1}$ with its formula and dividing through by $\log 3$
gives

$\displaystyle 0<\left|(n_{1}-1)\left(\dfrac{\log\alpha}{\log
3}\right)-m+\dfrac{\log(f_{k}(\alpha)(\alpha^{n-n_{1}}-1))}{\log
3}\right|<\dfrac{6}{\log 3}\cdot 3^{-(m-m_{1})}.$ (29)

As before, we keep the same
$\tau_{k},~{}~{}M_{k},~{}~{}(A_{k},B_{k}):=((6/\log 3),3)$ and put

$\displaystyle\mu_{k,l}:=\dfrac{\log(f_{k}(\alpha)(\alpha^{l}-1))}{\log
3},~{}~{}~{}~{}k\in[4,600],~{}~{}~{}~{}l:=n-n_{1}\in[1,600].$

We apply Lemma 2.3 to the inequality (29) 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}\leq 377$.

Next, we assume that $m-m_{1}\leq 375$. Here, we consider the inequality (22)
and also assume that $n-n_{1}\geq 20$. We put

$\displaystyle\Gamma_{2}:=(n-1)\log\alpha-m_{1}\log
3+\log\left(f_{k}(\alpha)/(3^{m-m_{1}}-1)\right).$

Thus, by the same arguments as before, we get

$\displaystyle 0<|\Gamma_{2}|<\dfrac{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

$\displaystyle 0<\left|(n-1)\left(\dfrac{\log\alpha}{\log
3}\right)-m_{1}+\dfrac{\log\left(f_{k}(\alpha)/(3^{m-m_{1}}-1)\right)}{\log
3}\right|<\dfrac{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

$\displaystyle\mu_{k,j}:=\dfrac{\log\left(f_{k}(\alpha)/(3^{m-m_{1}}-1)\right)}{\log
3},~{}~{}~{}~{}k\in[4,600],~{}~{}~{}j:=m-m_{1}\in[1,375].$

A computer search with Mathematica revealed that the maximum value of
$\lfloor\log(Aq/\varepsilon)/\log B\rfloor$, for $k\in[4,600]$ and
$j\in[1,375]$ is $<603$. Hence, $n-n_{1}\leq 603$.

To conclude the above computations, first we got that either $n-n_{1}\leq 600$
or $m-m_{1}\leq 375$. If $n-n_{1}\leq 600$, then $m-m_{1}\leq 377$, and if
$m-m_{1}\leq 375$, then $n-n_{1}\leq 603$. Therefore, we can conclude that we
always have

$\displaystyle n-n_{1}\leq 603~{}~{}~{}\text{ and }m-m_{1}\leq 377.$

Finally, we go to (24) and put

$\displaystyle\Gamma_{3}:=(n_{1}-1)\log\alpha-m_{1}\log
3+\log\left(\dfrac{f_{k}(\alpha)(\alpha^{n-n_{1}}-1)}{3^{m-m_{1}}-1}\right).$

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

$\displaystyle 0<|\Gamma_{3}|<\dfrac{2\cdot 3^{5}}{3^{0.8n}}.$

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

$\displaystyle 0<\left|(n_{1}-1)\left(\dfrac{\log\alpha}{\log
3}\right)-m_{1}+\dfrac{\log\left(f_{k}(\alpha)(\alpha^{n-n_{1}}-1)/(3^{m-m_{1}}-1)\right)}{\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

$\displaystyle\mu_{k,l,j}:=\dfrac{\log\left(f_{k}(\alpha)(\alpha^{l}-1)/(3^{j}-1)\right)}{\log
3},~{}~{}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
$\lfloor\log(1328q/\varepsilon)/\log 3\rfloor$, 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

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

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

######  Lemma 5.1.

For $1\leq n<2^{k/2}$ and $k\geq 10$, we have

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

######  Proof 5.2.

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

$|f_{k}(\alpha)\alpha^{n-1}-2^{n-2}|<\frac{2^{n}}{2^{k/2}}.$

By (11), we also have
$\left|F_{n}^{(k)}-f_{k}(\alpha)\alpha^{n-1}\right|<1/2$. Thus,

$\displaystyle|F_{n}^{(k)}-2^{n-2}|$ $\displaystyle\leq$
$\displaystyle|f_{k}(\alpha)\alpha^{n-1}-2^{n-2}|+|F_{n}^{(k)}-f_{k}(\alpha)\alpha^{n-1}|$
$\displaystyle<$
$\displaystyle\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)\leq\frac{2^{n}}{2^{k/2}}\left(1+\frac{1}{2^{k/2+3}}\right)$
$\displaystyle<$ $\displaystyle\frac{2^{n}\cdot
1.25}{2^{k/2}}=\left(\frac{5}{2^{k/2}}\right)2^{n-2}.$

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

$2^{n-2}(1+\zeta)-2^{n_{1}-2}(1+\zeta_{1})=3^{m}-3^{m_{1}},\qquad\max\\{|\zeta|,|\zeta_{1}|\\}<\frac{5}{2^{k/2}}.$

So,

$\displaystyle|2^{n-2}-3^{m}|$ $\displaystyle=$ $\displaystyle|-\zeta\cdot
2^{n-2}+2^{n_{1}-2}(1+\zeta_{1})-3^{m_{1}}|$ (30) $\displaystyle\leq$
$\displaystyle
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}}.$

Next, we have

$2^{n-2}>F_{n}^{(k)}-F_{n_{1}}^{(k)}=3^{m}-3^{m_{1}}\geq 2\cdot
3^{m-1},\quad{\text{\rm so}}\quad 2^{n-2}/3^{m}>2/3.$

Further,

$\displaystyle 3^{m}>3^{m}-3^{m_{1}}$ $\displaystyle=$ $\displaystyle
F_{n}^{(k)}-F_{n_{1}}^{(k)}\geq F_{n}^{(k)}-F_{n-1}^{(k)}$ $\displaystyle\geq$
$\displaystyle F_{n-2}^{(k)}>2^{n-4}\left(1-\frac{5}{2^{k/2}}\right)$
$\displaystyle>$ $\displaystyle 2^{n-4}\left(\frac{27}{32}\right)\quad(k>10),$

so

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

Going back to (30), 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,

$\displaystyle|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\\}.$
(32)

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

$\displaystyle\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\neq 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 (32) is bounded below as

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

By comparing with (32), we get

$\displaystyle\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),$

which implies that

$\displaystyle\min\\{(n-n_{1})\log 2,~{}~{}(m-m_{1})\log 3,~{}~{}(k/2)\log
2\\}<5.88\times 10^{8}(1+\log n).$ (34)

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

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

which implies that

$\displaystyle 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 (16) as

$\displaystyle|3^{m}-2^{n_{1}-2}(2^{n-n_{1}}-1)|$ $\displaystyle=$
$\displaystyle|3^{m_{1}}+2^{n-2}\zeta-2^{n_{1}-2}\zeta_{1}|$ $\displaystyle<$
$\displaystyle 3^{m_{1}}+2^{n-2}\left(\dfrac{10}{2^{k/2}}\right),$

which implies that

$\displaystyle\left|3^{m}2^{-n_{1}}(2^{n-n_{1}}-1)^{-1}-1\right|<20\max\left\\{\dfrac{1}{3^{m-m_{1}}},\dfrac{1}{2^{k/2}}\right\\}.$
(35)

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

$\Gamma_{1}=3^{m}2^{-(n_{1}-2)}(2^{n-n_{1}}-1)^{-1}-1,$ $\displaystyle
t:=3,\quad\gamma_{1}:=3,\quad\gamma_{2}:=2,\quad\gamma_{3}:=2^{n-n_{1}}-1,\quad
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\leq 4$ by classical results on
Catalan’s equation, which is a contradiction because $n\geq 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

$\displaystyle h(\gamma_{3})=h(2^{n-n_{1}}-1)\leq(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

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

By comparing with (35), we get

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

which implies that

$\displaystyle\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 (16) as

$\displaystyle|(3^{m_{1}}(3^{m-m_{1}}-1)-2^{n-2}|$ $\displaystyle=$
$\displaystyle|2^{n-2}\zeta-2^{n_{1}-2}(1+\zeta_{1})|$ $\displaystyle<$
$\displaystyle
2^{n-2}\left(\frac{5}{2^{k/2}}\right)+2^{n_{1}-2}\left(1+\frac{5}{2^{k/2}}\right),$

which implies that

$\displaystyle\left|3^{m_{1}}(3^{m-m_{1}}-1)2^{-(n-2)}-1\right|<20\max\left\\{\dfrac{1}{2^{n-n_{1}}},\dfrac{1}{2^{k/2}}\right\\}.$
(36)

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

$\Gamma_{2}=3^{m_{1}}2^{-(n-2)}(3^{m-m_{1}}-1)-1,$ $\displaystyle
t:=3,\quad\gamma_{1}:=3,\quad\gamma_{2}:=2,\quad\gamma_{3}:=(3^{m-m_{1}}-1),\quad
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 isn’t. 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

$\displaystyle h(\gamma_{3})=h(3^{m-m_{1}}-1)\leq(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

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

By comparing with (36), we get

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

which implies that

$\displaystyle\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 got

$\displaystyle\min\\{(n-n_{1})\log 2,~{}~{}(m-m_{1})\log 3,~{}~{}(k/2)\log
2\\}$ $\displaystyle<$ $\displaystyle 5.88\times 10^{8}(1+\log n)$
$\displaystyle\max\\{(n-n_{1})\log 2,~{}~{}(m-m_{1})\log 3,~{}~{}(k/2)\log
2\\}$ $\displaystyle<$ $\displaystyle 6.44\times 10^{19}(1+\log n)^{2}.$ (37)

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 (16) as

$\displaystyle\left|3^{m_{1}}(3^{m-m_{1}}-1)-2^{n_{1}-2}(2^{n-n_{1}}-1)\right|=|\zeta|\cdot
2^{n-2}+|\zeta_{1}|\cdot 2^{n_{1}-2}\leq
2^{n-2}\left(\frac{10}{2^{k/2}}\right),$

which implies that

$\displaystyle\left|3^{m_{1}}2^{-(n_{1}-2)}\left(\dfrac{3^{m-m_{1}}-1}{2^{n-n_{1}}-1}\right)-1\right|<\dfrac{20}{2^{k/2}}.$
(38)

We apply Matveev’s Theorem to

$\Gamma_{3}=3^{m_{1}}2^{-(n_{1}-2)}\left(\dfrac{3^{m-m_{1}}-1}{2^{n-n_{1}}-1}\right)-1,$

with the data

$\displaystyle
t=:3,\quad\gamma_{1}:=3,\quad\gamma_{2}:=2,\quad\gamma_{3}:=\left(\dfrac{3^{m-m_{1}}-1}{2^{n-n_{1}}-1}\right),\quad
b_{1}:=m_{1},\quad b_{2}:=-(n_{1}-2),\quad b_{3}:=1.$

Note that $\Gamma_{3}\neq 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 oder to
determine an acceptable value for $A_{3}$, note that

$\displaystyle h(\gamma_{3})$ $\displaystyle\leq$ $\displaystyle
h(3^{m-m_{1}}-1)+h(2^{n-n_{1}}-1)<(m-m_{1}+1)\log 3+(n-n_{1}+1)\log 2$
$\displaystyle<$ $\displaystyle 2\times 6.46\times 10^{19}(1+\log
n)^{2}<1.30\times 10^{20}(1+\log n)^{2}.$

Thus, we take $A_{3}:=1.30\times 10^{20}(1+\log n)^{2}$. By Theorem 2.2, we
have

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

By comparing with (38), we get

$\displaystyle(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}.$ (39)

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

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

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.3.

We have

$k<10^{41}\qquad{\text{and}}\qquad 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 (32) and let

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

Assume $m-m_{1}>1066$, $n-n_{1}>1690$ and $k>600$. Then, we note that (35) can
be rewritten as

$\displaystyle\left|e^{z}-1\right|<\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

$\displaystyle
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,

$\displaystyle 0<|z|\leq
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

$\displaystyle
0<|z|<2\max\\{2^{n_{1}-n+3},~{}~{}3^{m_{1}-m+2},~{}~{}2^{-k/2+3}\\}$ (41)

always holds. By replacing $z$ in the above inequality by its formula and
dividing through by $m\log 2$, we get that

$\displaystyle 0<\left|\dfrac{\log 3}{\log
2}-\dfrac{n}{m}\right|<\max\left\\{\dfrac{24}{2^{n-n_{1}}m},~{}~{}\dfrac{26}{3^{m-m_{1}}m},~{}~{}\dfrac{24}{2^{k/2}m}\right\\}.$
(42)

Then

$\displaystyle\max\left\\{\dfrac{24}{2^{n-n_{1}}m},~{}~{}\dfrac{26}{3^{m-m_{1}}m},~{}~{}\dfrac{24}{2^{k/2}m}\right\\}<\dfrac{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,\ldots,972$. Then $n/m=p_{l}/q_{l}$ implies
that $m=dq_{l}$ for some $d\geq 1$. Thus,

$\displaystyle\dfrac{1}{(a_{l+1}+2)q_{k}q_{l+1}}<\left|\dfrac{\log 3}{\log
2}-\dfrac{p_{l}}{q_{l}}\right|<\max\left\\{\dfrac{24}{2^{n-n_{1}}dq_{l}},~{}~{}\dfrac{26}{3^{m-m_{1}}dq_{l}},~{}~{}\dfrac{24}{2^{k/2}dq_{l}}\right\\}.$

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

$\displaystyle\min\\{2^{n-n_{1}},3^{m-m_{1}},2^{k/2}\\}\leq 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:

$\displaystyle n-n_{1}<1690,\qquad m-m_{1}<1066,\qquad k<3380.$

Suppose first that $m-m_{1}>10$ and $k\geq 20$, we go back to (35) and let

$\displaystyle z_{1}:=m\log 3-(n_{1}-2)\log 2-\log(2^{n-n_{1}}-1).$ (43)

Then we note that (35) can be rewritten as

$\displaystyle\left|e^{z_{1}}-1\right|<\max\\{3^{m_{1}-m+3},~{}~{}2^{-k/2+5}\\}.$

This implies that

$\displaystyle 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

$\displaystyle 0<\left|m\left(\dfrac{\log 3}{\log
2}\right)-(n_{1}-2)+\dfrac{\log(1/(2^{n-n_{1}}-1))}{\log
2}\right|<\max\\{98\cdot 3^{-(m-m_{1})},~{}~{}94\cdot 2^{-k/2}\\}.$

We put

$\displaystyle\tau:=\dfrac{\log 3}{\log
2},\qquad\mu:=\dfrac{\log(1/(2^{n-n_{1}}-1))}{\log
2},\qquad(A,B):=(78,3)\quad\text{ or }\quad(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}\leq 1078$ or $k\leq 3418$.

Next, we suppose that $n-n_{1}>10$, $k>20$ and go to (36) and let

$\displaystyle z_{2}:=m_{1}\log 3-(n-2)\log 2+\log(3^{m-m_{1}}-1).$ (44)

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

$\displaystyle\left|e^{z_{2}}-1\right|<\max\\{2^{n_{1}-n+5},~{}~{}2^{-k/2+5}\\}.$

This gives

$\displaystyle 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

$\displaystyle 0<\left|m_{1}\left(\dfrac{\log 3}{\log
2}\right)-(n-2)+\dfrac{\log(3^{m-m_{1}}-1)}{\log 2}\right|<\max\\{94\cdot
2^{-(n-n_{1})},~{}~{}94\cdot 2^{-k/2}\\}.$

We put

$\displaystyle\tau:=\dfrac{\log 3}{\log
2},\qquad\mu:=\dfrac{\log(3^{m-m_{1}}-1)}{\log 2},\qquad(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}\leq 1708$ or $k\leq 3416$.

Lastly, we assume that $k>20$ and go to (38) and let

$\displaystyle z_{3}:=m_{1}\log 3-(n_{1}-2)\log
2-\log((3^{m-m_{1}}-1)/(2^{n-n_{1}}-1)).$ (45)

We note that (38) can be rewritten as

$\displaystyle\left|e^{z_{3}}-1\right|<2^{-k/2+5}.$

This gives

$\displaystyle 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

$\displaystyle 0<\left|m_{1}\left(\dfrac{\log 3}{\log
2}\right)-(n_{1}-2)+\dfrac{\log((3^{m-m_{1}}-1)/(2^{n-n_{1}}-1))}{\log
2}\right|<94\cdot 2^{-k/2}.$

We put

$\displaystyle\tau:=\dfrac{\log 3}{\log
2},\qquad\mu:=\dfrac{\log((3^{m-m_{1}}-1)/(2^{n-n_{1}}-1))}{\log
2},\qquad(A,B):=(94,2),$

where $n-n_{1}\in[1,1708]$ 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\leq 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 several times by adjusting the values of $M$ with respect
to the new bounds of $n$. We summarise the data for the iterations performed
in Table 1

Table 1: Computation results | $M$ | $n-n_{1}\leq$ | $m-m_{1}\leq$ | $k\leq$
---|---|---|---|---
$1$ | $~{}10^{507}$ | $1708$ | $1074$ | $3428$
$2$ | $10^{88}$ | $~{}319$ | $~{}197$ | $~{}662$
$3$ | $10^{80}$ | $~{}287$ | $~{}180$ | $~{}590$
$4$ | $10^{79}$ | $~{}282$ | $~{}180$ | $~{}584$
$5$ | $10^{79}$ | $~{}282$ | $~{}180$ | $~{}584$

From the data displayed in the above table, 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 (7) with $k>600$.

## Acknowledgements

M. D. was supported by the Austrian Science Fund (FWF) grants: 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, 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.  Cambridge University Press, 2008.
  * [3] J.-J. Bravo, C.-A. Gómez, and F. Luca, On the distance between generalised Fibonacci numbers, Colloq. Math. 140 (2015), 107–118.
  * [4] J. J. Bravo, F. Luca, and K. Yazán, On Pillai’s problem with Tribonacci numbers and powers of 2,  Bul. Korean Math. Soc. 54 (2017), 1069–1080.
  * [5] J. J. Bravo and F. Luca, On a conjecture about repdigits in $k$-generalized Fibonacci sequences,  Publ. Math. Debrecen 82 (2013), 623–639.
  * [6] J. J. Bravo and F. Luca,  Powers of two in generalized Fibonacci sequences,  Rev. Colombiana Mat. 46 (2012), 67–79.
  * [7] K. C. Chim, I. Pink, and V. Ziegler,  On a variant of Pillai’s problem,  Int. J. Number Theory 13 (2017), 1711–1727.
  * [8] K. C. Chim, I. Pink and V. Ziegler.  On a variant of Pillai’s problem II.  Journal of Number Theory, 183 (2018), 269–290.
  * [9] 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
  * [10] M. Ddamulira,  On the problem of Pillai with Tribonacci numbers and powers of $3$,  J. Integer Sequences 22 (2019), Art. 19.5.6, 14pp.
  * [11] 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 (2017), 411–421.
  * [12] M. Ddamulira, C. A. Gómez-Ruiz, and F. Luca,  On a problem of Pillai with $k$-generalized Fibonacci numbers and powers of $2$,  Monatsh. Math. 187 (2018), 635–664.
  * [13] G. P. Dresden and Z. Du,  A simplified Binet formula for $r$-generalized Fibonacci numbers,  J. Integer Sequences 17 (2014), Art. 14.4.7, 9pp.
  * [14] A. Dujella and A. Pethő,  A generalization of a theorem of Baker and Davenport,  Quart. J. of Math. Oxford Ser. (2), 49 (1998), 291–306.
  * [15] 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.
  * [16] S. H. Hernández, F. Luca, and L. M. Rivera,  On Pillai’s problem with the Fibonacci and Pell sequences,  Bol. Soc. Mat. Mex. 25 (2019), 495–507.
  * [17] S. Gúzman Sánchez and F. Luca,  Linear combinations of factorials and $s$-units in a binary recurrence sequence.  Ann. Math. Qué. 38 (2014), 169–188.
  * [18] A. Herschfeld, The equation $2^{x}-3^{y}=d$,  Bull. Amer. Math. Soc. 41 (1935), 631.
  * [19] A. Herschfeld, The equation $2^{x}-3^{y}=d$,  Bull. Amer. Math. Soc. 42 (1936), 231–234.
  * [20] 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.
  * [21] P. Mihăilescu, Primary cyclotomic units and a proof of Catalan’s conjecture, J. Reine Angew. Math. 572 (2006), 167-195.
  * [22] S. S. Pillai, On $a^{x}-b^{y}=c$,  J. Indian Math. Soc. (N.S.) 2 (1936), 119–122.
  * [23] S. S. Pillai, A correction to the paper On $a^{x}-b^{y}=c$,  J. Indian Math. Soc. (N.S.) 2 (1937), 215.
  * [24] R. J. Stroeker and R. Tijdeman, Diophantine equations.  Computational Methods in Number Theory, Part II, 155, Math. Centre Tracts, Math. Centrum (Amsterdam) (1982), 321–369.