\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<b^{l_i}$, we have
$$
\overline{A_1\cdots A_t}_{(b)}
=b^{l_2+\cdots+l_t}A_1+b^{l_3+\cdots +l_t}A_2
+\cdots +b^{l_t}A_{t-1}+A_t\, .
$$
We always assume that $A_1\ne 0$, and in the special case
that $b=10$, we omit the subscript to simplify the notation.

In this paper, we study the set of positive integers $|u_n|$,
where $(u_n)_{n\ge 0}$ is a binary recurrent sequence,
that are the base-$b$ concatenations of other numbers of the form 
$|u_{n_j}|$, $j=1,\ldots,t$.  We show that if $t\ge 2$ is fixed,
then there are only finitely many instances of the equality
$$
|u_n|=\overline{|u_{n_1}|\cdots|u_{n_t}|}_{\,(b)}
$$
provided that the sequence $(u_n)_{n\ge 0}$ satisfies
certain mild hypotheses.  Note that some assumptions are clearly
needed in order to rule out certain obvious counterexamples;
for instance, the result does not hold for the sequence
$u_n=b^n-1$, $n\ge 0$, since the concatenation of any two
or more terms produces another term of the same sequence.

\begin{theorem}
\label{thm:1}
Let $u_n=c\alpha^n+d\beta^n$ be a nondegenerate binary recurrent
sequence of integers, and let $b\ge 2$ be a fixed integer base. 
Assume that $\dim_{\Z}\langle\log\alpha,~\log\beta,~\log b\rangle\ge 2$. 
Then for every fixed integer $t\ge 2$, there are at most finitely 
many positive integers $n$ for which the equality
\begin{equation}
\label{eq:concatenation1}
|u_n|={\overline{|u_{n_1}|
\mathop{\underbrace{0\cdots0}}\limits_{m_1}|u_{n_2}|
\mathop{\underbrace{0\cdots0}}\limits_{m_2}\cdots|u_{n_t}|
\mathop{\underbrace{0\cdots0}}\limits_{m_t}}}\vphantom{0}_{~(b)}
\end{equation}
holds for some nonnegative integers $n_1,\ldots,n_t$ and
$m_1,\ldots,m_t$ with $u_{n_1}\ne 0$.
\end{theorem}

Here, $\log(\cdot)$ stands for any fixed determination of the natural 
logarithm function, and
$\dim_{\Z}\langle\log\alpha,~\log\beta,~\log b\rangle$
denotes the rank of (the free part of) the additive subgroup of
$\C$ generated by $\{\log\alpha,~\log\beta,~\log b\}$.

Although our proof of Theorem~\ref{thm:1} is ineffective, this result 
can be seen as an extension of the aforementioned results of Senge
and Straus~\cite{SS1,SS2}.

In some special cases, one can employ effective methods to 
completely determine all the solutions to an equation such as 
\eqref{eq:concatenation1}.
Perhaps the best known example of a binary recurrent sequence
is the {\it Fibonacci sequence\/} $(F_n)_{n\ge 0}$, where
$F_0=0$ and $F_1=1$, and~\eqref{eq:recurrence} holds
with $r=s=1$. In this case, one has $\alpha=(1+{\sqrt {5}})/2$,
$\beta=-\alpha^{-1}$, $c=1/(\alpha-\beta)$, and $d=-c$.
For this special sequence, we obtain the
following computational result:

\begin{theorem}
\label{thm:2}
If $(m,n,k)$ is an ordered triple of nonnegative integers
with $m>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 i<j\le N$ 
can assume only finitely many values.

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

Let $\alpha_1$ and $\alpha_2$ be algebraic numbers.  Put
$\L=\Q[\alpha_1,\alpha_2]$, and let $D$ be the degree of $\L$ over $\Q$.
Let $A_1$ and $A_2$ be two positive integers such that
\begin{equation}
\label{eq:A_i}
\log A_i\ge \max\left\{h(\alpha_i),\frac{|\log \alpha_i|}{D},
\frac{1}{D}\right\}
\qquad\qquad (i=1,2).
\end{equation}
Here, for an algebraic number $\alpha$ whose minimal polynomial over 
$\Z$ is $a\prod_{i=1}^d(X-\alpha^{(i)})$, we write 
$h(\alpha)$ for the logarithmic height of $\alpha$, which is given by 
$$
h(\alpha)=\frac{1}{d}\left(\log|a|+
\sum_{i=1}^d\log\(\max\{1,|\alpha^{(i)}|\}\)\right).
$$ 
Let $b_1$ and $b_2$ be positive integers, and put 
$\Lambda=b_2\log \alpha_2-b_1\log \alpha_1$.  Finally, let
$$
b'=\frac{b_1}{D\log A_2}+\frac{b_2}{D\log A_1}.
$$
The following result is Corollaire~2 on page~288 of~\cite{LMN},
which gives an effective lower bound on the size of $\log|\Lambda|$:

\begin{theorem}
\label{thm:LMN}
Assume that $\alpha_1$ and $\alpha_2$ are real, positive, and 
multiplicatively independent. Then
$$
\log|\Lambda|\ge -24.34 D^4\(\max\left\{\log b'+0.14,\frac{21}{D},\frac{1}{2}
\right\}\)^2
\log A_1\log A_2.
$$
\end{theorem}

We also need a $p$-adic lower bound on $\Lambda$, that is,
an upper bound on the order at which a prime ideal ${\cal P}$ can
appear in the factorization of the principal ideal generated by
$\Lambda_1=\alpha_1^{b_1}-\alpha_2^{b_2}$ 
inside ${\cal O}_{\L}$.  For this, let $p$ be the prime number such that
${\cal P}\,|\,p$ (i.e., $p\Z={\cal P}\cap\Z$), and let $f$ be such that
the finite field ${\cal O}_{\L}/{\cal P}$ has $p^f$ elements.
Let $g$ be the smallest positive integer such that ${\cal P}$ divides
both $\alpha_1^g-1$ and $\alpha_2^g-1$.  Assume further 
that $A_i$ satisfies the inequality~\eqref{eq:A_i} as well 
as the inequality $\log A_i\ge f(\log p)/D$, for $i=1,2$.
The following result is an easy consequence of
Corollaire~2 on page~315 of~\cite{BL}:

\begin{theorem}
\label{thm:BL}
Assume that $\alpha_1$ and $\alpha_2$ are
multiplicatively independent. Then
\begin{eqnarray*}
\ord_{\cal P}\(\Lambda_1\) &\le& 
\frac{24pgD^5}{f^4(p-1)(\log p)^4}\\
&\times&\(\max\left\{\log b'+\log\log p+0.4,
\frac{10f\log p}{D},10\right\}\)^2\log A_1\log A_2.
\end{eqnarray*}
\end{theorem}

\section{Proof of Theorem~\ref{thm:1}}

Our proof of Theorem~\ref{thm:1} also treats the (slightly more
general) case in which we allow $t=1$, but in this case we add
the additional hypothesis that $m_1\ge 1$ (clearly, this condition
is needed to insure that the number of solutions
to~\eqref{eq:concatenation1} is finite).

Since $\alpha/\beta$ is not a root of unity, at most one element of
the sequence $(u_n)_{n\ge 0}$ is equal to $0$.  Hence, if $u_{n_i}=0$
for some $i$ in~\eqref{eq:concatenation1}, then $n_i$ is
uniquely determined. Note that $i\ne 1$.  If this happens, then
equation~\eqref{eq:concatenation1} can be viewed as an equation
of the same form, but with $t$ replaced by $t-1$ (and with only $2t-1$
unknowns).  Thus, to prove the theorem, it suffices to show
that there at most finitely many solutions to~\eqref{eq:concatenation1}
with $u_{n_i}\ne 0$, $i=1,\ldots,t$.

Let $\L=\Q[\alpha,\beta]$, and let ${\cal S}$ be the set of all 
infinite places of $\L$ and all finite places that divide $sb=-\alpha\beta b$. 
For a positive integer $m$, let $\ell_b(m)$ denote the number of
the digits in the base-$b$ representation of $m$.

Equation~\eqref{eq:concatenation1} is equivalent to
\begin{equation}
\label{eq:nonmainSuniteq}
|u_n|=\sum_{i=1}^t|u_{n_i}|b^{s_i},
\end{equation}
where
$$
s_i=\sum_{j=i}^t m_j+\sum_{j=i+1}^t\ell_b(|u_{n_j}|)
\qquad\qquad(i=1,\ldots,t).
$$
We remark that, if $n=n_i$ for some $i$,
it follows that $t=1$ (since each $u_{n_i}\ne 0$)
and $s_1=m_1=0$ (since $b\ge 2$), which contradicts our assumption
that $m_1\ge 1$ when $t=1$.  Hence, $n\ne n_i$ for all $i=1,\ldots,t$.
Now write~\eqref{eq:nonmainSuniteq} in the form
\begin{equation}
\label{eq:mainSuniteq}
\varepsilon_0(c\alpha^{n}+d\beta^n)=
\sum_{i=1}^t\varepsilon_i\(c\alpha^{n_i}+d\beta^{n_i}\)b^{s_i},
\end{equation}
where $\varepsilon_i\in \{\pm 1\}$ for $i=0,\ldots,t$.

Suppose first that $n_i>n-\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 $m<n$. Furthermore, any 
such prime $p$ satisfies  $p\equiv \pm 1 \mod n$.
\end{lemma}

Next, we record the following estimate for the function
$\ell(n)=\ell_{10}(F_n)$, which gives the number of digits in
the decimal expansion of $F_n$:

\begin{lemma}
\label{lem:length}
For all $n\ge 1$, we have
$$
\frac{(n-2)\log\alpha}{\log 10}<\ell(n)
\le\frac{(n-1)\log\alpha}{\log 10}+1.
$$
\end{lemma}

\begin{proof}
By induction on $k$, it is easy to see that 
$\alpha^{k-2}\le F_k\le\alpha^{k-1}$ holds for all $k\ge 1$.
Since $\ell(k)$ is the unique integer for which
$10^{\ell(k)-1}\le F_k<10^{\ell(k)}$, the result follows.
\end{proof}

We keep the notation used in the proof of Theorem~\ref{thm:1}.
In particular, $\L=\Q(\sqrt{5}\,)$, ${\cal O}_{\L}=\Z[\alpha]$,
and $D=2$ is the degree of $\L$ over $\Q$.  Notice that 
${\cal O}_{\L}$ is a UFD. We also put $\varpi={\sqrt {5}}$ and
${\cal P}=[\varpi]$; then $[p]=[5]={\cal P}^2$,
and $f=1$. We need the following elementary lemma:

\begin{lemma}
\label{lem:valuation}
If $r\ge 2$, we have
$$
\ord_{\cal P}(\alpha^r-1)\le\frac{2\log(r/4)}{\log 5}+1.
$$
The same inequality holds with $\alpha$ replaced by $\beta$.
\end{lemma}

\begin{proof}
The inequality for $\beta$ follows from the one for $\alpha$ by 
conjugation. Note that the right hand side of the stated inequality 
is positive for all $r\ge 2$. Since
$$
\alpha=\frac{1+\sqrt{5}}{2}\equiv 2^{-1}\pmod\varpi,
$$
it follows that ${\ord}_{\cal P}(\alpha^r-1)=0$ 
if $4\nmid r$; hence, it suffices
to assume that $4\,|\,r$ in what follows.  Since
$$
\alpha^4-1=\frac{5+3\sqrt{5}}{2},
$$
it follows that ${\ord}_{\cal P}(\alpha^4-1)=1$. Thus, we may write
$\alpha^4=1+\varpi u$, where $u$ is coprime to $\varpi$. 
If $s\ge 1$ is an integer and $5\nmid s$, then
$$
\alpha^{4s}-1=(\alpha^4-1)\sum_{j=0}^{s-1}\alpha^{4j}
=\varpi u\sum_{j=0}^{s-1}(1+\varpi u)^j
\equiv\varpi us\pmod \varpi,
$$
which shows that $\ord_{\cal P}(\alpha^{4s}-1)=1$ as well. 
One checks similarly that if $s\ge 1$ and $5\nmid s$, 
then $\ord_{\cal P}(\alpha^{20s}-1)=3$.

We now claim that, for all $t\ge 0$ and $s\ge 1$ such that $5\nmid s$, 
we have 
\begin{equation}
\label{eq:claim}
\ord_{\cal P}(\alpha^{4s\cdot 5^t}-1)=2t+1.
\end{equation}
To prove this, we use induction on the parameter $t$. Since
the claim is true for $t=0$ or $1$, let us suppose that
$t\ge 2$.  Then,
\begin{eqnarray*}
\alpha^{4s\cdot 5^t}-1
&=&(\alpha^{4s\cdot 5^{t-1}}-1)
\sum_{j=0}^4\alpha^{4sj\cdot 5^{t-1}}\\
&=&5(\alpha^{4s\cdot 5^{t-1}}-1)+
(\alpha^{4s\cdot 5^{t-1}}-1)
\sum_{j=1}^4(\alpha^{4sj\cdot 5^{t-1}}-1).
\end{eqnarray*}
By the induction hypothesis, we have
$$
\ord_{\cal P}\(5(\alpha^{4s\cdot 5^{t-1}}-1)\)=2+\(2(t-1)+1\)=2t+1,
$$
while
$$
\ord_{\cal P}\((\alpha^{4s\cdot 5^{t-1}}-1)
\sum_{j=1}^4(\alpha^{4sj\cdot 5^{t-1}}-1)\)
\ge 2\(2(t-1)+1\)=4t-2>2t+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, $m<n-1$, for otherwise
$$
F_k=F_m\cdot 10^{\ell(n)}+F_n>1000F_{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, $t<r$. 
Thus, $\alpha^r-1=2^{\lambda} \alpha^t$.  By conjugation, we also have 
$\beta^r-1=2^{\lambda} \beta^t$.  Subtracting
these two equations and dividing the result by $\alpha-\beta$,
we obtain that $F_r=2^{\lambda}F_t$. If $r\ge 13$, 
this equation is impossible in view of Lemma~\ref{lem:prim_div}.
The fact that $F_r=2^{\lambda}F_t$ is also impossible for
$5\le r\le 13$ can be checked by hand, and the result follows. 
\end{proof}

We are now ready to embark on the proof of Theorem \ref{thm:2}.
For this, let $(m,n,k)$ be a fixed triple of nonnegative integers
for which $\overline{F_mF_n}=F_k$ holds. We 
note that $n>0$, since for $n=0$ we have $10F_m=F_k$, 
which has no positive integer solutions $(m,k)$ 
(by Lemma~\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}
<b''=\frac{\ell(n)}{4\log\alpha}+\frac{k}{20}.
$$
Using Theorem \ref{thm:LMN}, we get that 
$$
|(k-m)\log\alpha-\ell(n)\log 10|\ge
\exp\left(-864\(\max\{\log b''+0.14,10.5\}\)^2\right).
$$
Combining the above estimates, we derive the bound
\begin{equation}
\label{eq:2nd est}
r<\frac{\log 10}{\log\alpha}+\frac{864}{\log\alpha}
\(\max\{\log b''+0.14,10.5\}\)^2.
\end{equation}

Now, if $k>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}