\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{amsthm}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf Concatenations with Binary Recurrent Sequences}
\vskip 1cm
\large
William D.~Banks \\
Department of Mathematics \\
University of Missouri \\
Columbia, MO 65211\\
USA \\
\href{mailto:bbanks@math.missouri.edu}{\tt bbanks@math.missouri.edu} \\
\ \\
Florian~Luca\\
Instituto de Matem{\'a}ticas\\
Universidad Nacional Aut\'onoma de M{\'e}xico\\
C.P.~58089 \\
Morelia, Michoac{\'a}n \\
M{\'e}xico\\
\href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx}\\
\end{center}
\vskip .2 in
\begin{abstract}
Given positive integers $A_1,\ldots,A_t$ and $b\ge 2$,
we write $\overline{A_1\cdots A_t}_{(b)}$ for the integer
whose base-$b$ representation is the concatenation
of the base-$b$ representations of $A_1,\ldots,A_t$.
In this paper, we prove that if $(u_n)_{n\ge 0}$ is
a binary recurrent sequence of integers satisfying some mild
hypotheses, then for every fixed integer $t\ge 1$,
there are at most finitely many nonnegative integers $n_1,\ldots,n_t$
such that ${\overline{|u_{n_1}|\cdots |u_{n_t}|}}_{\,(b)}$ is
a member of the sequence $(|u_n|)_{n\ge 0}$. In particular,
we compute all such instances in the special case that $b=10$, $t=2$,
and $u_n=F_n$ is the sequence of Fibonacci numbers.
\end{abstract}
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{proposition}{Proposition}[section]
%\newtheorem{corollary}{Corollary}[section]
%\newtheorem{lemma}{Lemma}[section]
%\documentclass[12pt]{article}
%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,
% latexsym,amsopn,amstext,amsxtra,euscript,amscd}
\renewcommand{\theequation}{\arabic{equation}}
\newtheorem{prop}{Proposition}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{corollary}[cor]{Corollary}
\newtheorem{conj}[prop]{Conjecture}
\newtheorem{defi}[prop]{Definition}
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{fac}[prop]{Fact}
\newtheorem{facs}[prop]{Facts}
\newtheorem{com}[prop]{Comments}
\newtheorem{prob}{Problem}
\newtheorem{problem}[prob]{Problem}
\newtheorem{ques}{Question}
\newtheorem{question}[ques]{Question}
\newtheorem{remark}[prop]{Remark}
\def\ord{{\mathrm{ord}}}
\def\scr{\scriptstyle}
\def\\{\cr}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\langle}
\def\>{\rangle}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\rf#1{\left\lceil#1\right\rceil}
\def\lcm{{\rm lcm\/}}
\def\C{\mathbb C}
\def\R{\mathbb R}
\def\Q{{\mathbb Q}}
\def\F{{\mathbb F}}
\def\Z{{\mathbb Z}}
\def\cO{{\mathcal O}}
\def\ord{{\mathrm{ord}}}
\def\Nm{{\mathrm{Nm}}}
\def\L{{\mathbb L}}
\def\xxx{\vskip5pt\hrule\vskip5pt}
\def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt}
\section{Introduction}
A result of Senge and Straus~\cite{SS1, SS2}
asserts that if $b_1,b_2\ge 2$ are
multiplicatively independent integers, there are at most finitely
many positive integers with the property that the sum of the digits
in each of the two bases $b_1$ and $b_2$ lies below any
prescribed bound. An effective version of this statement
is due to Stewart~\cite{Stew}, who gave a lower
bound on the overall sum of the digits of $n$ in base $b_1$
and in base $b_2$. A somewhat more general version of
Stewart's result has been obtained by Luca~\cite{Lu}.
A variety of arithmetical questions about integers whose base-$b$
digits satisfy certain restrictions has been considered by many authors;
see, for example, \cite{BaCoSh,BaHaSa,BaSh,EMS1,EMS2,FilKon,FoMa1,
FoMa2,FrSh,Gel,Kon,KoMaSa,Luca,Lu,MaSa1,MaSa2,Shp}
and the references contained therein. Here, we consider integers
whose base-$b$ digits are formed by concatenating
(absolute values of) terms in a binary recurrent sequence.
Let $(u_n)_{n\ge 0}$ be a {\it binary recurrent sequence\/} of integers;
i.e., a sequence of integers satisfying the recurrence relation
\begin{equation}
\label{eq:recurrence}
u_{n+2}=ru_{n+1}+su_n\qquad\qquad(n\ge 0),
\end{equation}
where $r$ and $s$ are nonzero integers with $r^2+4s\ne 0$.
It is well known that if $\alpha$ and $\beta$ are the
roots of the equation $x^2-rx-s=0$, then $u_n=c\alpha^n+d\beta^n$
holds for all $n\ge 0$, where $c$ and $d$ are constants given by
$$
c=\frac{-\beta u_0+u_1}{\alpha-\beta}\qquad\text{and}\qquad
d=\frac{\alpha u_0-u_1}{\alpha-\beta}.
$$
Throughout the paper, we assume that $(u_n)_{n\ge 0}$ is
{\it nondegenerate\/} (i.e., $\alpha/\beta$ is not a root of $1$,
and $\alpha\beta cd\ne 0$). Reordering the roots if necessary,
we can further assume that $|\alpha|\ge|\beta|$ and $|\alpha|>1$.
Let $b\ge 2$ be a fixed integer base.
Given positive integers $A_1,\ldots,A_t$,
we denote by $\overline{A_1\cdots A_t}_{(b)}$ the integer whose base-$b$
representation is equal to the concatenation (in order) of the base-$b$
representations of $A_1,\ldots,A_t$. Thus, if $l_i$ is the
smallest positive integer such that $A_i**0$ and such that $\overline{F_mF_n}=F_k$, then
$F_k\in\big\{13,21,55\}$.
\end{theorem}
Throughout the paper, we use the Vinogradov symbols $\ll$ and $\gg$,
as well as the Landau symbol $O$, with the understanding that the
implied constants are computable and depend at most on the given data.
\section{Preliminaries}
\label{sec:prel}
Let $\L$ be an algebraic number field of degree $D$ over $\Q$.
Denote by ${\cal O}_{\L}$ the ring of algebraic integers and
by ${\cal M}_{\L}$ the set of places. For a fractional ideal
${\cal I}$ of $\L$, let $\Nm_{\L}({\cal I})$ be the usual norm;
we recall that $\Nm_{\L}({\cal I})=\#({\cal O}_{\L}/{\cal I})$ if
${\cal I}$ is an ideal of ${\cal O}_{\L}$, and the norm map is
extended multiplicatively (using unique factorization) to
all of the fractional ideals of $\L$.
For a prime ideal ${\cal P}$, we denote by $\ord_{\cal P}(x)$
the order at which ${\cal P}$ appears in the ideal factorization
of the principal ideal $[x]$ generated by $x$ in $\L$.
For a place $\mu\in{\cal M}_{\L}$ and a number $x\in\L$, we
define the absolute value $|x|_{\mu}$ as follows:
\begin{itemize}
\item[$(i)$] $|x|_{\mu}=|\sigma(x)|^{1/D}$
if $\mu$ corresponds to a real embedding $\sigma:\L\to\R$;
\item[$(ii)$] $|x|_{\mu}=|\sigma(x)|^{2/D}=|{\overline{\sigma}}(x)|^{2/D}$
if $\mu$ corresponds to some pair of complex
conjugate embeddings $\sigma,{\overline{\sigma}}:\L\to \C$;
\item[$(iii)$] $|x|_{\mu}=\Nm_{\L}({\cal P})^{-\ord_{\cal P}(x)/D}$
if $\mu$ corresponds to a nonzero prime
ideal ${\cal P}$ of ${\cal O}_{\L}$.
\end{itemize}
In the case $(i)$ or $(ii)$, we say that $\mu$ is {\it real infinite\/} or
{\it complex infinite\/}, respectively; in the case $(iii)$,
we say that $\mu$ is {\it finite\/}.
The set of absolute values are well known to satisfy
the following {\it product formula\/}:
\begin{equation}
\label{eq:product}
\prod_{\mu\in {\cal M}_{\L}} |x|_\mu=1,\qquad\text{~for all~}x\in\L^*.
\end{equation}
One of our principal tools is the following simplified version
of a result of Schlickewei~\cite{Schm1,Schm2},
which is commonly known as the {\it Subspace Theorem\/}:
\begin{theorem}
\label{lem:S-unit}
Let $\L$ be an algebraic number field of degree $D$.
Let ${\cal S}$ be a finite set of places of $\L$ containing all
the infinite ones. Let $\{L_{1,\mu},\ldots,L_{N,\mu}\}$ for
$\mu\in{\cal S}$ be linearly independent sets of
linear forms in $N$ variables with coefficients in $\L$.
Then, for every fixed $0<\varepsilon<1$, the set
of solutions ${\bf x}=(x_1,\ldots,x_N)\in\L^N\backslash\{{\bf 0}\}$
to the inequality
\begin{equation}
\label{eq:fundineq}
\prod_{\mu\in {\cal S}}\prod_{i=1}^N
|L_{i,\mu}({\bf x})|_{\mu}\le
\left({\rm max}\{|x_i|:i=1,\ldots,N\}\right)^{-\varepsilon}
\end{equation}
is contained in finitely many proper linear subspaces of $\L^N$.
\end{theorem}
Let ${\cal S}$ be a finite subset of ${\cal M}_{\L}$ containing all the
infinite places. An element $x\in \L$ is called a {\it ${\cal S}$-unit\/}
if $|x|_\mu=1$ for all $\mu\not\in{\cal S}$. An equation of the form
\begin{equation}
\label{eq:Suniteq}
\sum_{i=1}^N a_i x_i=0,
\end{equation}
where each $a_i\in \L^*$, is called an
{\it ${\cal S}$-unit equation} if each $x_i$ is an ${\cal S}$-unit;
it is said to be {\it nondegenerate\/}
if no proper subsum of the left hand side vanishes.
It is clear that if ${\bf x}=(x_1,\ldots,x_N)$
is a solution of the ${\cal S}$-unit equation~\eqref{eq:Suniteq}, and
$\rho$ is a ${\cal S}$-unit in $\L^*$, then
$\rho{\bf x}=(\rho x_1,\ldots,\rho x_N)$ is a also a solution
of~\eqref{eq:Suniteq}; in this case, the solutions ${\bf x}$ and
$\rho{\bf x}$ are said to be {\it equivalent}.
We recall the following result of Schlickewei~\cite{Schlick1}
(see also~\cite{ESS}) on ${\cal S}$-unit equations:
\begin{theorem}
\label{thm:evSS}
Let $a_1,\ldots,a_N$ be fixed numbers in $\L^*$.
Then the ${\cal S}$-unit equation~\eqref{eq:Suniteq}
has only finitely many equivalence classes of nondegenerate
solutions $(x_1,\ldots,x_N)$. Moreover, the number of such
equivalence classes is bounded by a constant that depends only on
$N$ and the cardinality of ${\cal S}$.
\end{theorem}
An immediate consequence of Theorem \ref{thm:evSS} is that if
${\bf x}=(x_1,\ldots,x_N)$ is a solution of the ${\cal S}$-unit equation
\eqref{eq:Suniteq}, then the ratios $x_i/x_j$ for $1\le in-\kappa$ for some $i\in\{1,\ldots,t\}$,
where $\kappa\ge 0$ is a constant to be specified later.
{From} \eqref{eq:nonmainSuniteq}, we have that
$|u_n|\ge|u_{n_i}|b^{s_i}$.
It is known that the estimate $|u_m|=|\alpha|^{m+O(\log m)}$
holds for all positive integers $m\ge 2$ (see
Theorem~3.1 on page~64 in~\cite{ST}). Moreover,
if $\alpha$ is real, then $|\alpha|>|\beta|$, and one has
the estimate $|u_m|=|\alpha|^{m+O(1)}$. Therefore,
since $|\alpha|>1$, the following bound holds if $n_i>n-\kappa$:
\begin{equation}
\label{eq:maxlogbound}
\max\{n_i-n,s_i\}\ll\left\{\begin{array}{ll}
1,&\quad\text{if $\alpha\in\R$};\\
\log n,&\quad\text{if $\alpha\not\in\R$~~
(i.e., $\alpha=\overline\beta\,)$}.\end{array}\right.
\end{equation}
Next, we show that if $n_i\le n-\kappa$ for every $i=1,\ldots,t$,
then there exists an index $i\in\{1,\ldots,t\}$ for which
the following bound holds:
\begin{equation}
\label{eq:maxlogbound2}
\max\{n-n_i,s_i\}\ll 1.
\end{equation}
To do this, we first observe that~\eqref{eq:mainSuniteq} is
an ${\cal S}$-unit equation with $N=2t+2$ terms,
coefficients $(a_1,\ldots,a_N)=(c,d, -c,-d,\ldots,-c,-d)$,
and the \hbox{${\cal S}$-unit} unknowns ${\bf x}=(x_1,\ldots,x_N)=
(\varepsilon_0\alpha^n,\varepsilon_0\beta^n,\varepsilon_1
\alpha^{n_1}b^{s_1},\ldots,\varepsilon_t\beta^{n_t}b^{s_t}).$
If the ${\cal S}$-unit equation \eqref{eq:mainSuniteq} is nondegenerate,
then $x_1/x_2=(\alpha/\beta)^n$ can assume only finitely many
values; since $\alpha/\beta$ is not a root of unity, it follows that $n$
can take at most finitely many values.
On the other hand, if the ${\cal S}$-unit equation~\eqref{eq:mainSuniteq}
is degenerate, let $E_1$ and $E_2$ be two (not necessarily distinct)
nondegenerate subequations of~\eqref{eq:mainSuniteq}
that contain the unknowns $x_1=\varepsilon_0\alpha^n$
and $x_2=\varepsilon_0\beta^n$, respectively.
Clearly, $E_1$ and $E_2$ can be chosen in at most finitely many ways.
The preceding argument shows that $n$ can assume only finitely
many values if the unknowns $x_1$ and $x_2$ both lie in $E_1$
or both lie in $E_2$. Therefore, we may assume that $E_1$ does
not contain $x_2$, and $E_2$ does not contain $x_1$.
We now distinguish the following cases:
\begin{itemize}
\item[$(i)$]
{\it $E_1$ contains an unknown of the form
$x_{2i+1}=\varepsilon_i \alpha^{n_i}b^{s_i}$
for some $i\ge 1$ and $E_2$ contains an unknown of the form
$x_{2j}=\varepsilon_j \beta^{n_j}b^{s_j}$ for some $j\ge 2$\/}.
In this case, both $x_1/x_{2i+1}=\pm \alpha^{n-n_i}b^{-s_i}$ and
$x_2/x_{2j}=\pm \beta^{n-n_j}b^{-s_j}$ can assume only finitely many values.
Since $\dim_{\Z}\langle \log \alpha,\log \beta, \log b\rangle\ge 2$, it
follows that either the pair $(\alpha,b)$ or the pair $(\beta,b)$
is multiplicatively independent; thus, either $\max\{n-n_i,s_i\}\ll 1$
or $\max\{n-n_j,s_j\}\ll 1$.
\item[$(ii)$]
{\it $E_1$ contains only unknowns of the form
$x_{2i}=\varepsilon_i \beta^{n_i}b^{s_i}$ with $i\ge 2$
(except for $x_1$) and $E_2$ contains only unknowns of the form
$x_{2j+1}=\varepsilon_j \alpha^{n_j}b^{s_j}$ with $j\ge 1$
(except for $x_2$)\/}.
For each choice of the indices $i$ and $j$, both
$x_1/x_{2i}=\pm \alpha^{n}\beta^{-n_i}b^{-s_i}$
and $x_2/x_{2j+1}=\pm\beta^n\alpha^{-n_j}b^{-s_j}$
can have at most finitely many values.
Since we may assume that $n$ takes infinitely many values (otherwise,
there is nothing to prove), it follows that there exist
numbers $n^*$, $n_i^*$, $n_j^*$, $s_i^*$, and $s_j^*$
such that both relations
\begin{equation}
\label{eq:double_fun}
\begin{split}
\alpha^{n}\beta^{-n_i}b^{-s_i}&=\alpha^{n^*}\beta^{-n^*_i} b^{-s^*_i},\\
\beta^n\alpha^{-n_j}b^{-s_j}&=\beta^{n^*}\alpha^{-n^*_j}b^{-s^*_j},
\end{split}
\end{equation}
hold for arbitrarily large values of $n$. Among all possible choices
for the quintuple $(n^*,n_i^*,n_j^*,s_i^*,s_j^*)$ of such numbers,
we fix one for which $n_i^*$ is as small as possible; thus,
$n_i\ge n_i^*$ whenever the relations~\eqref{eq:double_fun} hold.
Since there are only finitely many possibilities for $E_1$ and $E_2$
and (once these are fixed) for the indices $i$ and $j$,
we obtain in this way a finite list of such quintuples
$(n^*,n_i^*,n_j^*,s_i^*,s_j^*)$. Hence, the constant $\kappa$ can be
initially chosen such that the inequality
$\kappa>\max\{n^*-n_i^*,n^*-n_j^*\}$ holds in all cases.
Now let $E_1$, $E_2$, $i$, and $j$ be fixed, and suppose that
the relations~\eqref{eq:double_fun} hold with $n>n^*$.
Taking logarithms, we obtain that
\begin{eqnarray*}
(n-n^*)\log \alpha & = & (n_i-n_i^*)\log \beta+(s_i-s_i^*)\log b,\\
(n-n^*)\log \beta & = &(n_j-n_j^*)\log \alpha+
(s_j-s_j^*)\log b.
\end{eqnarray*}
Let $v_1=(n_i-n_i^*)/(n-n^*)$ and $v_2=(n_j-n_j^*)/(n-n^*)$,
and note that both numbers are rational. Since we are assuming
that $n_i\le n-\kappa$ for $i=1,\ldots,t$, it follows that
$$
n^*-n_i^*<\kappa\le n-n_i,
$$
which implies that $v_1<1$. Similarly, $v_2<1$. Since $n_i\ge n_i^*$
by our choice of the quintuple $(n^*,n_i^*,n_j^*,s_i^*,s_j^*)$,
we also see that $v_1\ge 0$. These statements together imply that
$v_1v_2\ne 1$, which is all we need. {From} the preceding relations,
we obtain that
$$
\log \alpha=v_1\log \beta+w_1\log b
=v_1(v_2\log \alpha+w_2\log b)+w_1\log b,$$
where $w_1=(s_i-s_i^*)/(n-n^*)$ and $w_2=(s_j-s_j^*)/(n-n^*)$
are rational numbers. Since $v_1v_2\ne 1$, this implies that
$\log\alpha/\log b$ is rational. Similarly, we see that
$\log\beta/\log b$ is rational. But these statements
contradict our hypothesis that
$\dim_{\Z}\langle\log\alpha,\log\beta,\log b\rangle\ge 2$;
therefore, $n$ is bounded, and it follows that
$n_i$, $n_j$, $s_i$, and $s_j$ are bounded as well.
\item[$(iii)$] {\it The remaining cases\/}.
For the remaining cases, there are only two possibilities:
\begin{itemize}
\item[$\bullet$] {\it $E_1$ contains
an unknown of the form $x_{2i+1}=\varepsilon_i \alpha^{n_i}b^{s_i}$
for some $i\ge 1$ and $E_2$ contains only unknowns of the form
$x_{2j+1}=\varepsilon_j \alpha^{n_j}b^{s_j}$ with $j\ge 1$ (except
for $x_2$)\/}.
\item[$\bullet$] {\it $E_1$ contains only unknowns of the form
$x_{2i}=\varepsilon_i \beta^{n_i}b^{s_i}$ with $i\ge 2$ (except for
$x_1$) and $E_2$ contains an unknown of the form $x_{2j}=\varepsilon_j
\beta^{n_j}b^{s_j}$ for some $j\ge 2$\/}.
\end{itemize}
We treat only the first case, as the second case is similar.
We note that the ratio $x_1/x_{2i+1}=\pm \alpha^{n-n_i}b^{-s_i}$
assumes only finitely many values. If $\alpha$ and $b$ are multiplicatively
independent, it follows that both $n-n_i$ and $s_i$ are bounded,
and we are done. On the other hand, if $n-n_i$ is not bounded,
it follows that $\log \alpha/\log b$ is rational.
If $j$ is such that $x_{2j+1}\in E_2$, then
$x_2/x_{2j+1}=\pm\beta^{n}\alpha^{-n_j}b^{-s_j}$ can take at most
finitely many values. Since $\alpha$ and $b$ are multiplicatively
dependent, $\beta$ and $b$ must be multiplicatively independent,
and it follows that $n$ can take only finitely many values.
But this is impossible if $n-n_i$ is unbounded.
\end{itemize}
The analysis above completes our proof that~\eqref{eq:maxlogbound2}
holds for some $i$ in the case that
$n_i\le n-\kappa$ for all $i=1,\ldots,t$.
Combining~\eqref{eq:maxlogbound}
and~\eqref{eq:maxlogbound2}, we see that the bound
\begin{equation}
\label{eq:maxlogbound3}
\max\{|n-n_i|,s_i\}\ll\left\{\begin{array}{ll}
1,&\quad\text{if $\alpha\in\R$};\\
\log n,&\quad\text{if $\alpha\not\in\R$~~
(i.e., $\alpha=\overline\beta\,)$}\end{array}\right.
\end{equation}
holds for some $i\in\{1,\ldots,t\}$ in every case.
We now select $i$ such that~\eqref{eq:maxlogbound3} holds
and rewrite~\eqref{eq:mainSuniteq} in the form
\begin{equation}
\label{eq:intermediaryeq}
c\alpha^n+d\beta^n+Ab^{s_{i-1}}
+c_1\alpha^{n_i}b^{s_i}+d_1\beta^{n_i}b^{s_i}+B=0,
\end{equation}
where $c_1=-\varepsilon_i\varepsilon_0 c$,
$d_1=-\varepsilon_i\varepsilon_0 d$,
$$
A=-\sum_{j=1}^{i-1}\varepsilon_j\varepsilon_0 u_{n_j}b^{s_j-s_{i-1}}
\qquad\text{and}\qquad
B=-\sum_{j=i+1}^t \varepsilon_i\varepsilon_0 u_{n_j} b^{s_j}.
$$
Since
$$
b^{s_{i-1}}\ge |u_{n_i}|\ge |\alpha|^{n_i+O(\log n_i)}
=|\alpha|^{n+O(\log n)},
$$
we see that $A=\exp(O(\log n))$. Similarly, since $b^{s_i}\ge B$,
it follows that $B=\exp(O(\log n))$.
Assume first that both $n-n_i$ and $s_i$ are bounded (this is the case,
for instance, if $\L$ is real). In this case, $A$ and $B$ are bounded
as well; hence, we can assume that they are fixed.
Here,~\eqref{eq:intermediaryeq} becomes
\begin{equation}
\label{eq:someequation}
C_1\alpha^n+D_1\beta^n+Ab^{s_{i-1}}+B=0,
\end{equation}
where $C_1=c+c_1\alpha^{n_i-n}$ and $D_1=d+d_1\beta^{n_i-n}$ can also
be regarded as fixed numbers.
The case $A=B=C_1=D_1=0$ leads to $i=t=1$,
$\alpha^{n-n_i}=-cc_1^{-1}=\pm 1$
and $\beta^{n-n_i}=-dd_1^{-1}=\pm 1$; therefore, $t=1$, $n=n_1$,
and $m_1=0$, which contradicts our assumption that $m_1\ge 1$
when $t=1$. Consequently, the equation~\eqref{eq:someequation}
is nontrivial. If any two of the coefficients $A,~B,~C_1,~D_1$
are zero, then either $n$ or $s_{i-1}$ is bounded, and this leads
to at most finitely many possibilities for $n$. A similar argument
based on Theorem~\ref{thm:evSS} can be used if one of the
coefficients $A,~B,~C_1,~D_1$ is zero, or if $ABC_1D_1\ne 0$, to
show that there are at most finitely many possibilities for $n$.
Thus, from now on, we can suppose that either $n-n_i$ or $s_i$ is
unbounded over the set of solutions to~\eqref{eq:intermediaryeq}.
In this case, $\alpha$ and $\beta$ are complex conjugates.
Assume first that $B\ne 0$ in equation \eqref{eq:intermediaryeq}.
Suppose also that $A\ne 0$.
We apply Theorem \ref{lem:S-unit} with $N=5$, the linear
forms $L_{j,\mu}({\bf x})=x_j$ for each $j=1,\ldots,5$,
and $\mu\in {\cal S}$, except when $j=1$ and $\mu$ is infinite,
in which case we take $L_{1,\mu}({\bf x})=cx_1+dx_2+x_3+c_1x_4+d_1x_5$
(note that, as $\L$ is complex quadratic, there is
only one infinite place). We evaluate the
double product appearing in Theorem~\ref{lem:S-unit} for our
system of forms and the points
${\bf x}=(\alpha^n,\beta^n,Ab^{s_{i-1}},\alpha^{n_i}b^{s_i},
\beta^{n_i}b^{s_i})$. Clearly,
\begin{equation}
\label{eq:part1}
\prod_{\mu\in {\cal S}}|L_{j,\mu}({\bf x})|=1
\end{equation}
if $j\in\{2,4,5\}$, since $x_2$, $x_4$ and $x_5$ are ${\cal S}$-units.
Moreover,
\begin{equation}
\label{eq:part2}
\prod_{\mu\in {\cal S}}|L_{3,\mu}({\bf x})|\le A=\exp(O(\log n)).
\end{equation}
Finally, since $x_1$ is an ${\cal S}$-unit, it follows from
the product formula \eqref{eq:product} that
\begin{equation}
\label{eq:part3}
\prod_{\substack{\mu\in {\cal S}\\\mu~\text{finite}}}
|L_{1,\mu}({\bf x})|_{\mu}=
\frac{1}{|\Nm_\L(\alpha^n)|}\le \frac{1}{|\alpha|^n},
\end{equation}
while by equation \eqref{eq:intermediaryeq}, we have
\begin{equation}
\label{eq:part4}
\prod_{\substack{\mu\in {\cal S}\\\mu~{\rm is~infinite}}}
|L_{1,\mu}({\bf x})|_{\mu}=B^2\le \exp(O(\log n)).
\end{equation}
Multiplying the estimates \eqref{eq:part1},
\eqref{eq:part2}, \eqref{eq:part3} and
\eqref{eq:part4}, we derive that
\begin{equation}
\label{eq:ineqdouble}
\prod_{j=1}^N\prod_{\mu\in {\cal S}}|L_{j,\mu}({\bf x})|
\le \frac{AB^2}{\alpha^{n}}\le
\exp\(-n\log \alpha+O(\log n)\).
\end{equation}
Since $\max\{|x_j|:j=1,\ldots,N\}=|\alpha|^n$, the inequality
\eqref{eq:ineqdouble} together with Theorem~\ref{lem:S-unit}
(for example, with $\varepsilon=1/2$ and $n>n_{\varepsilon}$),
imply that there exist finitely many proper subspaces of $\L^N$
containing all solutions ${\bf x}$. Thus, the relation
\begin{equation}
\label{eq:intermediaryeq1}
C_2\alpha^n+D_2\beta^n+C_3\alpha^{n_i}b^{s_i}+D_3\beta^{n_i}b^{s_i}+
EAb^{s_i-1}=0
\end{equation}
holds for some fixed coefficients $C_2$, $D_2$, $C_3$, $D_3$ and $E$
in $\L$, which are not all equal to zero.
If $A=0$, then the same argument with $N=4$ also
yields an identity of the shape~\eqref{eq:intermediaryeq1}.
Finally, if $B=0$, then~\eqref{eq:intermediaryeq} is the same as
\eqref{eq:intermediaryeq1} with $C_2=c$, $D_2=d$, $C_3=c_1$, $D_3=d_1$,
and $E=1$. Clearly, we may assume that $C_2$ and $D_2$ are conjugate
(over $\L$), that $C_3$ and $D_3$ are conjugate (over $\L$), and that
$E\in \Z$ (if not, we can conjugate \eqref{eq:intermediaryeq1} and
subtract the result from \eqref{eq:intermediaryeq1} to obtain a
``shorter'' nontrivial equation of the same type with the
desired properties).
If $E=0$, then \eqref{eq:intermediaryeq1} is a ${\cal S}$-unit equation.
If it is nondegenerate, we see that $\alpha^n\beta^{-n}$ can take only
finitely many values; since $\alpha/\beta$ is not a root of unity,
there are at most finitely many possibilities for $n$.
If the ${\cal S}$-unit equation is degenerate, then either
$C_2=D_2=0$, in which case $n_i$ can take only finitely many values
(and since $|n-n_i|\ll \log n$, it follows that $n$ is bounded as well),
or $C_2D_2\ne 0$ but $C_3=D_3=0$, in which case $n$ can again take
only finitely many values, or $C_2C_3D_2D_3\ne 0$. In the last case,
either $\alpha^{n-n_i}b^{-s_i}$ and $\beta^{n-n_i}b^{-s_i}$ can take
only finitely many values, or $\alpha^n \beta^{-n_i}b^{-s_i}$ and
$\beta^n\alpha^{-n_i}b^{-s_i}$ can take only finitely many values;
but these are cases that have already been considered.
Finally, we are left with the possibility that $E\ne 0$, in which case
we can assume that $E=1$. We now rewrite \eqref{eq:intermediaryeq1}
in the form
\begin{equation}
\label{eq:lastone}
C_4\alpha^n+D_4\beta^n=-Ab^{s_{i-1}},
\end{equation}
where $C_4=C_2+C_3\alpha^{n_i-n}b^{s_i}$ and
$D_4=D_2+D_3\beta^{n_i-n}b^{s_i}$.
Since $C_4$ and $D_4$ are conjugated in $\L$, it follows that they are
simultaneously zero or nonzero.
Assume first that $C_4=D_4=0$. Then both
relations
\begin{equation}
\label{eq:***}
C_2=-C_3\alpha^{n-n_i}b^{s_i}\qquad {\text{\rm and}}\qquad
D_2=-D_3\beta^{n-n_i}b^{s_i}
\end{equation}
hold. If $C_2=0$ then $C_3=0$ (by \eqref{eq:***}), $D_2=0$ (because
$C_2$ and $D_2$ are conjugated), and therefore $D_3=0$ (by \eqref{eq:***});
together with equation \eqref{eq:intermediaryeq1}, these lead to $E=0$,
which is a contradiction. Thus, $C_2\ne 0$, and the preceding
argument implies that $C_2C_3D_2D_3\ne 0$. Now, equation \eqref{eq:***}
together with our hypothesis that
$\dim_{\Q}\langle \log \alpha,\log \beta,\log b\rangle\ge 2$
lead to the conclusion that both $n-n_i$ and $s_i$ are
bounded, which is a case already treated.
We now assume that $C_4D_4\ne 0$. Let $\ell=\gcd(r^2,s)$, where $r$ and $s$
are the coefficients of the recurrence \eqref{eq:recurrence}. Set
$\alpha_1=\alpha^2/\ell,~\beta_1=\beta^2/\ell$. Applying
Lemma~A.10 on page 20 in \cite{ST}, we see that $\alpha_1$ and $\beta_1$
are algebraic integers and that the principal ideals they generate in
$\L$ are coprime. Clearly, $\alpha_1$ and $\beta_1$ are complex
conjugates, and $|\alpha_1|>1$. Write $n=2m+\delta$, where
$\delta\in \{0,1\}$. Put $(C_5,D_5)=(C_4,D_4)$ if $\delta=0$
and $(C_5,D_5)=(\alpha C_4,\beta D_4)$ if $\delta=1$.
Dividing both sides of equation~\eqref{eq:lastone}
by $\ell^m$, we see that the expression
$$
C_5\alpha_1^m+D_5\beta_1^m
$$
is a rational number such that every prime factor of its numerator
or denominator divides either $Ab\alpha\beta$ or one of the denominators
of $C_2$, $D_2$, $C_3$, or $D_3$. Let ${\cal P}=\{p_1,\ldots,p_v\}$ be
the set consisting of all of these primes, and write
$$
C_5\alpha^m+D_5\beta^m=\prod_{i=1}^v p_i^{r_i}.
$$
We now bound the order $r_i$ of $p_i$. Let $\pi_i$ be some prime ideal of
$\L$ lying above $p_i$. If $\pi_i|\alpha_1$, then
$\ord_{\pi_i}(\alpha_1^m)\ge m\ge n/2-1$. On the other hand, it is clear
that
$$
\max\{|\ord_{\pi_i}(C_5)|,|\ord_{\pi_i}(D_5)|\}
\ll \max\{|n-n_i|,s_i\}\ll \log n.
$$
Thus, for large $n$, we get that
\begin{equation}
\label{eq:ineq1}
\ord_{\pi_i}(C_5\alpha_1^m+D_5\beta_1^m)=\ord_{\pi_i}(D_5\beta_1^m)=
\ord_{\pi_i}(D_5)\ll \log n,
\end{equation}
since $\alpha_1$ and $\beta_1$ are coprime.
A similar analysis can be used if $\pi_i|\beta_1$. Assume now that $\pi_i$
does not divide $\alpha_1\beta_1$.
Then
$$
r_i=\ord_{\pi_i}\(C_5\alpha_1^m+D_5\beta_1^m\)=
\ord_{\pi_i}(C_5\beta_1^m)+\ord_{\pi_1}\((\alpha_1/\beta_1)^m-(-D_5/C_5)\).
$$
Certainly,
$$
\ord_{\pi_i}(C_5\beta_1^m)=\ord_{\pi_i}(C_5)\ll \log n,
$$
while from Theorem \ref{thm:BL}, we deduce that
$$
\ord_{\pi_i}\((\alpha_1/\beta_1)^m-(-D_5/C_5)\)\ll (\log n)^2 |\log |C_5||
\ll (\log n)^3.
$$
Thus,
\begin{equation}
\label{eq:ineq2}
\ord_{\pi_i}(C_5\alpha_1^m+D_5\beta_1^m)\ll (\log n)^3
\end{equation}
in this case. Comparing inequalities \eqref{eq:ineq1} and \eqref{eq:ineq2},
we see that inequality \eqref{eq:ineq2} always holds. Since this is true
for all $i=1,\ldots,v$, we conclude that
\begin{equation}
\label{eq:ineq3}
\log|C_5\alpha_1^m+D_5\beta_1^m|\le \sum_{i=1}^v r_i\log p_i\ll (\log n)^3.
\end{equation}
On the other hand, we have
$$
\log|C_5\alpha_1^m+D_5\beta_1^m|=\log|C_5|+m\log|\alpha_1|+\log|1+(D_5C_5^{-1}
(\beta_1\alpha_1^{-1})^m|.
$$
Clearly,
\begin{equation}
\label{eq:4}
\log|C_5|\gg -\log n,
\end{equation}
and using Theorem \ref{thm:LMN}, we get that
\begin{equation}
\label{eq:5}
\log|1+(D_5C_5^{-1})
(\beta_1\alpha_1^{-1})^m|\gg -(\log n)^2|\log |C_5||.
\end{equation}
Putting together inequalities
\eqref{eq:ineq3}, \eqref{eq:4}, \eqref{eq:5}, and using the fact that
$m\gg n$ and $|\alpha_1|>1$, we obtain that
$$
n\ll (\log n)^3,
$$
which shows that $n$ can take only finitely many values.
This completes the proof of Theorem~\ref{thm:1}.
\section{Proof of Theorem~\ref{thm:2}}
Before proceeding to the proof of Theorem \ref{thm:2}, we gather
a few useful facts about the Fibonacci sequence.
We first recall the following special case of the {\it Primitive
Divisor Theorem\/}, which is due to Carmichael~\cite{Carm}:
\begin{lemma}
\label{lem:prim_div}
For all $n\ge 13$, there exists a prime factor $p$ of $F_n$ such that
$p$ does not divide $F_m$ for any positive integer $m2t+1,
$$
and~\eqref{eq:claim} follows.
Finally, writing $r$ in the form
$r=4s\cdot 5^t$, where $t\ge 0$, $s\ge 1$, and $5\nmid s$,
we have
$$
\ord_{\cal P}(\alpha^r-1)=2t+1=\frac{2\log(r/4s)}{\log 5}+1
\le\frac{2\log(r/4)}{\log 5}+1,
$$
which finishes the proof.
\end{proof}
\begin{lemma}
\label{lem:m_r bounds}
If $(m,n,k)$ is an ordered triple of positive integers such
that $\overline{F_mF_n}=F_k$, and $(m,n,k)\ne(1,4,7)$ or $(2,4,7)$,
then $m\ge 3$ and $k-n\ge 4$.
\end{lemma}
\begin{proof} Suppose that $n\ge 13$.
First, suppose that $m=1$ or $m=2$. Then
$10^{\ell(n)}+F_n=F_k$; hence,
$2F_n\le F_k\le 11F_n$, which (by simple estimates)
implies that $n+2\le k\le n+5$. Since $n\ge 13$, we have that
$\ell(n)\ge 3$, and thus,
$$
F_n\equiv F_k\pmod 8.
$$
An analysis of the sequence of Fibonacci numbers modulo $8$ shows that
this congruence is not possible when $k= n+4$ or $k=n+5$;
therefore, $k=n+2$ or $k=n+3$. If $k=n+2$, then
$10^{\ell(n)}=F_{n+1}$, while for $k=n+3$, we have $10^{\ell(n)}=2F_{n+1}$.
However, by Lemma~\ref{lem:prim_div}, there
exists a prime $p\ge n$ dividing $F_{n+1}$, which is not
possible in our cases. Consequently, if $m\le 2$, we must have $n\le 12$.
Checking the remaining possibilities, the only solutions found
are $(1,4,7)$ and $(2,4,7)$.
Assuming now that
$\overline{F_mF_n}=F_k$, $n\ge 15$, and $k\le n+3$, we then have
\begin{equation}
\label{eq:cases}
F_m\cdot 10^{\ell(n)}=F_k-F_n=\left\{\begin{array}{ll}
F_{n-1},&\quad\text{if $k=n+1$};\\
F_{n+1},&\quad\text{if $k=n+2$};\\
2F_{n+1},&\quad\text{if $k=n+3$}.\end{array}\right.
\end{equation}
Moreover, $m1000F_{n-1}>F_{n+3},
$$
contradicting our assumption that $k\le n+3$.
Using Lemma~\ref{lem:prim_div} again, we see that there exist
primes $p\,|\,F_{n-1}$ and $q\,|\,F_{n+1}$ with $\gcd(pq,F_m)=1$
and $\min\{p,q\}\ge 13$, which is not possible in view of~\eqref{eq:cases}.
Hence, if $k\le n+3$, we must have $n\le 14$, and thus $k\le 17$.
Examining these possibilities reveals no solutions other than
the two found in the previous case.
\end{proof}
\begin{lemma}
\label{lem:mult_indep}
If $r\ge 1$ is even, then
$$
\frac{\alpha^r-1}{\beta^r-1}=-\alpha^r,
$$
while if $r\ge 5$ is odd, then the numbers $(\alpha^r-1)/(\beta^r-1)$
and $\alpha$ are multiplicatively independent.
\end{lemma}
\begin{proof}
The first statement is trivial since $\alpha\beta=-1$. For the second
statement, we note that if $r$ is odd then
$$
\frac{\alpha^r-1}{\beta^r-1}=-\alpha^r\left(\frac{\alpha^r-1}{\alpha^r+1}
\right).
$$
We now observe that if ${\cal D}$ is the common divisor in ${\cal O}_{\L}$
of $\alpha^r-1$ and $\alpha^r+1$, then ${\cal D}~|~2$. Since $2$ is inert
in ${\cal O}_{\L}$, it follows that ${\cal D}\in \{1,2\}$. The above arguments
show that if $(\alpha^r-1)/(\beta^r-1)$ and $\alpha$ are multiplicatively
dependent, then so are $(\alpha^r-1)/(\alpha^r+1)$ and $\alpha$.
Using the fact that ${\cal O}_{\L}$ is a UFD
and the computation of ${\cal D}$,
it follows that $\alpha^r-1$ is either a unit, or it is an associate
of~$2$. Hence, we get an equation of the form
$$
\alpha^r-1=\pm 2^{\lambda}\alpha^t
$$
with integers $\lambda\in \{0,1\}$ and $t$. Since $r>3$, it follows
that $\alpha^r-1>\alpha^3-1>2$; hence, the sign in this equation
is positive, and $t\ge 1$. Clearly, $t0$, since for $n=0$ we have $10F_m=F_k$,
which has no positive integer solutions $(m,k)$
(by Lemma~\ref{lem:prim_div}, for example). Put $r=k-n$, and
assume that $k>10^6$. By Lemma~\ref{lem:m_r bounds}, we can
further suppose that $m\ge 3$ and $r\ge 4$.
Since $\beta=-1/\alpha$, we have
\begin{eqnarray*}
F_m\cdot 10^{\ell(n)}=F_k-F_n
&=&\varpi^{-1}(\alpha^k-\beta^k-\alpha^n+\beta^n)\\
&=&\varpi^{-1}(\alpha^n(\alpha^r-1)-\beta^n(\beta^r-1))\\
&=&\varpi^{-1}\alpha^n(\beta^r-1)
\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\).
\end{eqnarray*}
Consequently,
\begin{equation}
\label{eq:v relation}
\ord_{\cal P}(F_m)+2\ell(n)=-1+\ord_{\cal P}(\beta^r-1)
+\ord_{\cal P}\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\).
\end{equation}
Assume first that $r$ is odd. We apply Theorem \ref{thm:BL} with
the choices $\alpha_1=(\alpha^r-1)/(\beta^r-1)$,\break
$\alpha_2=-\alpha^{-2}$, $b_1=1$, and $b_2=n$.
The condition that $\alpha_1$ and $\alpha_2$ are multiplicatively\break
independent is satisfied by Lemma~\ref{lem:mult_indep} because $r\ge 5$.
Furthermore, note that
$$
h(\alpha_1)
\le\tfrac{1}{2}\(\log|(\alpha^r-1)(\beta^r-1)|+\log|\alpha_1|\)
\le\tfrac{1}{2}\log\alpha^{2r}=r\log\alpha,
$$
and $h(\alpha_2)=\log\alpha$. Since $r\ge 5$,
we can choose $A_1=\alpha^r$ and $A_2=\varpi$; hence,
$$
b'=\frac{1}{\log 5}+\frac{n}{2r\log\alpha}
\le \frac{1}{2\log\alpha}+\frac{n}{10\log\alpha}
\le\frac{3n}{4\log\alpha}.
$$
Finally, as $\alpha\equiv\beta\pmod\varpi$, and
$\ord_{\cal P}(\alpha^r-1)=\ord_{\cal P}(\beta^r-1)=0$
(by Lemma~\ref{lem:valuation}),
it follows that ${\cal P}$ divides $\alpha_1-1$. Moreover,
noting that $-\alpha^{-2}\equiv
1\pmod \varpi$, it follows that ${\cal P}$ also divides $\alpha_2-1$.
Thus, we can take $g=1$. By Theorem~\ref{thm:BL},
we obtain the bound
\begin{eqnarray*}
\lefteqn{\ord_{\cal P}
\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\)}\\
&&\qquad\qquad\le \frac{480r\log\alpha}{(\log 5)^3}
\(\max\left\{\log n+\log\(\frac{3\log 5}{4\log\alpha}\)
+0.4,10\right\}\)^2\\
&&\qquad\qquad\le 56r\(\max\left\{\log n+2,10\right\}\)^2.
\end{eqnarray*}
Next, consider the case that $r$ is even; then
$$
\frac{\alpha^r-1}{\beta^r-1}-(\alpha^{-2})^n
=-\alpha^r-(-\alpha^2)^n=(-1)^{n+1}\alpha^{-2n}
(\alpha^{k+n}\pm 1),
$$
and the last expression divides $\alpha^{2k+2n}-1$ in ${\cal O}_{\L}$;
hence, by Lemma \ref{lem:valuation}, we obtain that
$$
\ord_{\cal P}\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\)
\le \frac{2\log((k+n)/2)}{\log 5}+1.
$$
Substituting the estimates above into~\eqref{eq:v relation}, and
applying Lemmas~\ref{lem:length} and~\ref{lem:valuation},
we derive that
\begin{equation}
\label{eq:1st est}
2\frac{(n-2)\log\alpha}{\log 10}<\ell(n)
\le\frac{2\log(r/4)}{\log 5}+
56r\(\max\left\{\log n+2,10\right\}\)^2,
\end{equation}
if $r$ is odd, and
\begin{equation}
\label{eq:1st est2}
2\frac{(n-2)\log\alpha}{\log 10}<\ell(n)
\le\frac{2\log(r/4)}{\log 5}+\frac{2\log((k+n)/2)}{\log 5}+1,
\end{equation}
if $r$ is even.
{From} the equality $\overline{F_mF_n}=F_k$, we also see that
\begin{equation}
\label{eq:ident}
\alpha^m\cdot 10^{\ell(n)}-\alpha^k
=\beta^m\cdot 10^{\ell(n)}-\alpha^n+\beta^n-\beta^k,
\end{equation}
and, since $10^{\ell(n)}<10F_n$ and $m\ge 3$, we have
\begin{equation}
\label{eq:xx}
\begin{split}
|\alpha^{m-k}\cdot 10^{\ell(n)}-1|
&=\alpha^{-k}|
\beta^m\cdot 10^{\ell(n)}-\alpha^n+\beta^n-\beta^k|\\
&\le\alpha^{-k}(10|\beta|^3F_n+\alpha^n+2)
<4\alpha^{-r}.
\end{split}
\end{equation}
Since $m\ge 3$, both sides of~\eqref{eq:ident} are {\it negative\/},
and since $r\ge 4$, we have $4\alpha^{-r}<\tfrac{3}{5}$; thus,
$$
\tfrac{2}{5}<\alpha^{m-k}\cdot 10^{\ell(n)}<1.
$$
It follows that
\begin{equation}
\label{eq:yy}
|\alpha^{m-k}\cdot 10^{\ell(n)}-1|
>\tfrac{2}{5}|(k-m)\log\alpha-\ell(n)\log 10|.
\end{equation}
We now apply Theorem \ref{thm:LMN} with the choices
$\Lambda=(k-m)\log\alpha-\ell(n)\log 10$,
$\alpha_1=10$, $\alpha_2=\alpha$, $b_1=\ell(n)$, and
$b_2=k-m$. Here,
$h(\alpha_1)=\log 10$ and $h(\alpha_2)=\tfrac{1}{2}\log\alpha$; hence,
we can choose $A_1=10$, and $A_2=\alpha^2$, and
$$
b'=\frac{\ell(n)}{4\log\alpha}+\frac{k-m}{20}
****2n$, then, by Lemma~\ref{lem:length}, we have
$$
b''=\frac{\ell(n)}{4\log\alpha}+\frac{k}{20}
\le\frac{n-1}{4\log 10}+\frac{1}{4\log\alpha}+\frac{k}{20}
<\frac{(k/2)-1}{4\log 10}+\frac{1}{4\log\alpha}+\frac{k}{20},
$$
and $r=k-n>k/2$; hence, the inequality~\eqref{eq:2nd est} is
not possible for $k>500000$. On the other hand, if $k\le 2n$, then
$$
b''=\frac{\ell(n)}{4\log\alpha}+\frac{k}{20}
\le\frac{n-1}{4\log 10}+\frac{1}{4\log\alpha}+\frac{n}{10}.
$$
When $r$ is even, estimate ~\eqref{eq:1st est2} gives
$$
\frac{(n-2)\log \alpha}{\log 10}<\frac{\log(n/4)}{\log 5}+\frac{\log(3n/2)}
{\log 5}+\frac{1}{2},
$$
which implies that $n<20$; hence, $k<40$.
When $r$ is odd, by
combining the inequalities~\eqref{eq:1st est}, and~\eqref{eq:2nd est},
we obtain a contradiction unless $n\le 1.1\times 10^{11}$ and
$k\le 2n\le 2.2\times 10^{11}$.
Although the preceding argument shows that there are only finitely
many solutions $(m,n,k)$ to the equation $\overline{F_mF_n}=F_k$,
it would be computationally infeasible to search for solutions over
the entire range $k\le 2.2\times 10^{11}$. In order to reduce
the range further, we use a standard technique involving the continued
fraction expansion of $(\log 10)/(\log\alpha)$.
Suppose that $n\le 1.1\times 10^{11}$ and $r\ge 56$.
By~\eqref{eq:xx} and~\eqref{eq:yy}, we have
$$
\left|\frac{\log 10}{\log\alpha}-\frac{(k-m)}{\ell(n)}\right|
<\frac{10}{\alpha^r\ell(n)}\le\frac{1}{2\ell(n)^2}.
$$
Here, the last inequality is equivalent to $20\ell(n)\le\alpha^r$,
which holds (by Lemma~\ref{lem:length}) for this choice of parameters.
By well known properties of continued fractions,
it follows that the fraction
$(k-m)/\ell(n)$ is a convergent of $(\log 10)/(\log\alpha)$.
Writing $(k-m)/\ell(n)=p_j/q_j$ for some $j\ge 0$, where
$p_j/q_j$ denotes the $j$th convergent to $(\log 10)/(\log \alpha)$,
and using Lemma~\ref{lem:length} again to bound $\ell(n)$
for $n$ in our range, we see that
$q_j\le\ell(n)\le 2.3\times 10^{10}$, which implies that $j\le 23$.
Noting that
$$
10\alpha^{-r}>|\ell(n)\log 10-(k-m)\log\alpha|
\ge\min_{1\le j\le 23}|q_j\log 10-p_j\log\alpha|>1.6\times 10^{-11},
$$
we conclude that $r\le 57$. Substituting this estimate
into~\eqref{eq:1st est}, we derive the more tractable upper bound
$n\le 2.1\times 10^6$.
At this point, we turn to the computer. Note that if $n\ge 74$,
one has $\ell(n)\ge 15$; therefore, if $\overline{F_mF_n}=F_k$,
it follows that $F_n\equiv F_k\pmod{10^{15}}$. However, a computer
search quickly reveals that there is no solution to this congruence
with $74\le n\le 2.1\times 10^6$ and $k\le n+57$. Thus,
it remains only to search for solutions $(m,n,k)$ with $n\le 73$
and $k\le n+57$, and one obtains only solutions with $k=7$, $8$ or $10$;
that is $F_k\in\{13,21,55\}$.
This completes the proof of Theorem~\ref{thm:2}.
\section{Acknowledgements}
The authors wish to thank the referee for his detailed and
insightful comments on the original manuscript, which led to
improvements in the quality, accuracy, and completeness of the paper.
This work was done during a visit by the second author
to the University of Missouri, Columbia; the hospitality and
support of this institution are gratefully acknowledged.
During the preparation of this paper,
W.~B.\ was supported in part by NSF grant DMS-0070628, and
F.~L.\ was supported in part by grants
SEP-CONACYT 37259-E and 37260-E.
\begin{thebibliography}{99}
\bibitem{BaCoSh} W.~Banks, A.~Conflitti and I.~E.~Shparlinski,
Character sums over integers with restricted $g$-ary digits,
{\it Illinois J.\ Math.\/} {\bf 46} (2002), 819--836.
\bibitem{BaHaSa} W.~Banks, D.~Hart and M.~Sakata,
Almost all palindromes are composite,
{\it Math.\ Res.\ Lett.\/} {\bf 11} (2004), 853--868.
\bibitem{BaSh} W.~Banks and I.~E.~Shparlinski,
On the number of sparse RSA exponents,
{\it J.\ Number Theory\/} {\bf 95} (2002), 340--350.
\bibitem{BL} Y.~Bugeaud and M.~Laurent,
Minoration effective de la distance \hbox{$p$-adique} entre puissances
de nombres alg\'ebriques,
{\it J.\ Number Theory\/} {\bf 61} (1996), 311--342.
\bibitem{Carm} R.~D.~Carmichael,
On the numerical factors of the arithmetic forms
$\alpha\sp n1\beta\sp n$,
{\it Ann.\ of Math.\ (2)\/} {\bf 15} (1913/14), 30--70.
\bibitem{EMS1} P.~Erd{\H o}s, C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On arithmetic properties of integers with missing digits, I,
{\it J.\ Number Theory\/} {\bf 70} (1998), 99--120.
\bibitem{EMS2} P.~Erd{\H o}s, C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On arithmetic properties of integers with missing digits, II,
{\it Discrete Math.\/} {\bf 200} (1999), 149--164.
\bibitem{ESS} J.-H.~Evertse, H.~P.~Schlickewei and W.~M.~Schmidt,
Linear equations with variables which lie in a multiplicative group,
{\it Ann.\ of Math.\ (2)} {\bf 155} (2002), 807--836.
\bibitem{FilKon} M.~Filaseta and S.~V.~Konyagin,
Squarefree values of polynomials all of whose coefficients are
$0$ and $1$,
{\it Acta Arith.\/} {\bf 74} (1996), 191--205.
\bibitem{FoMa1} E.~Fouvry and C.~Mauduit,
Meth\'odes des crible et fonctions sommes des chiffres,
{\it Acta Arith.\/} {\bf 77} (1996), 339--351.
\bibitem{FoMa2} E.~Fouvry and C.~Mauduit,
Sommes des chiffres et nombres presque premiers,
{\it Math.\ Ann.\/} {\bf 305} (1996), 571--599.
\bibitem{FrSh} J.~B.~Friedlander and I.~E.~Shparlinski,
On the distribution of Diffie--Hellman triples
with sparse exponents,
{\it SIAM J.\ Discrete Math.\/} {\bf 14} (2001), 162--169.
\bibitem{Gel} A.~O.~Gel'fond,
Sur les nombres qui ont des propri\'et\'es additives
et multiplicatives donn\'ees,
{\it Acta Arith.\/} {\bf 13} (1968), 259--265.
\bibitem{Kon} S.~V.~Konyagin,
Arithmetic properties of integers with missing digits:
distribution in residue classes,
{\it Period.\ Math.\ Hungar.\/} {\bf 42} (2001), 145--162.
\bibitem{KoMaSa} S.~V.~Konyagin, C.~Mauduit and A.~S\'ark\H ozy,
On the number of prime factors of integers
characterized by digit properties,
{\it Period.\ Math.\ Hungar.\/} {\bf 40} (2000), 37--52.
\bibitem{Lu} F.~Luca,
Distinct digits in base $b$ expansions of linear
recurrence sequences,
{\it Quaest.\ Math.\/} {\bf 23} (2000), 389--404.
\bibitem{Luca} F.~Luca,
Arithmetic properties of positive integers with fixed digit sum,
to appear in {\it Rev.\ Mat.\ Iberoamericana}.
\bibitem{MaSa1} C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On the arithmetic structure of sets characterized
by sum of digits properties,
{\it J.\ Number Theory\/} {\bf 61} (1996), 25--38.
\bibitem{MaSa2} C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On the arithmetic structure of the integers whose
sum of digits is fixed,
{\it Acta Arith.\/} {\bf 81} (1997), 145--173.
\bibitem{LMN}
M.~Laurent, M.~Mignotte and Y.~Nesterenko,
Formes lin\'eaires en deux logarithmes et
d\'eterminants d'interpolation,
{\it J.\ Number Theory\/} {\bf 55} (1995), 285--321.
\bibitem{Schlick1}
H.~P.~Schlickewei,
$S$-unit equations over number fields,
{\it Invent.\ Math.\/} {\bf 102} (1990), 95--107.
\bibitem{Schm1} W.~M.~Schmidt,
{\it Diophantine Approximations\/},
Springer Verlag, LNM {\bf 785} (1980).
\bibitem{Schm2} W.~M.~Schmidt,
{\it Diophantine Approximations and Diophantine Equations\/},
Springer Verlag, LNM {\bf 1467} (1991).
\bibitem{SS1} H.~G.~Senge and E.~G.~Straus,
${\rm PV}$-numbers and sets of multiplicity, in
{\it Proceedings of the Washington State Conference in Number Theory
(Washington State Univ., Pullman, Wash., 1971)\/},
55--67, Dept.\ Math.\ Washington State Univ.,
Pullman, Washington, 1971.
\bibitem{SS2} H.~G.~Senge and E.~G.~Straus,
${\rm PV}$-numbers and sets of multiplicity,
in ``Collection of articles dedicated to the memory
of Alfr\'ed R\'enyi, II'',
{\it Period.\ Math.\ Hungar.\/} {\bf 3} (1973), 93--100.
\bibitem{ST} T.~N.~Shorey and R.~Tijdeman,
{\it Exponential diophantine equations\/},
Cambridge Univ.\ Press, 1986.
\bibitem{Shp} I.~E.~Shparlinski,
Prime divisors of sparse integers,
{\it Period.\ Math.\ Hungar.\/} {\bf 46} (2003), 215--222.
\bibitem{Stew} C.~L.~Stewart,
On the representation of an integer in two different bases,
{\it J.\ Reine Angew.\ Math.\/} {\bf 319} (1980), 63--72.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B37; Secondary 11B39, 11J86 .
\noindent \emph{Keywords: } binary recurrent sequences,
Fibonacci numbers, digits.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received August 30 2004;
revised version received January 13 2005.
Published in {\it Journal of Integer Sequences},
January 14 2005. Small revisions, January 17 2005.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in
\end{document}
**