%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%       Attila Peth\H{o}
%    	Diophantine properties of linear recursive sequences II.
%	2000.12.04
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[12pt]{article}
%    ----------------------------
\input amssym.def
\input amssym.tex
\font\frak=eufb10
\textheight23cm
 \textwidth16cm 
\oddsidemargin0cm 
\evensidemargin0cm
\topmargin0cm
\topskip0cm
 \footskip1.5cm 
\headheight0cm
\let\di \displaystyle
\let \ks\relax
\let\ks\scriptstyle
\def \N {{\rm l}\!{\rm N}}
\def \Z {{\Bbb Z}}
\def \Q {{\Bbb Q}}
\def \R {{\Bbb R}}
\def \C {{\Bbb C}}
\def \K {{\Bbb K}}
\def \L {{\Bbb L}}
\def \ZK {\Z_{\K}}
\def \eps {\varepsilon}
\newtheorem{lemma}{Lemma}
\newenvironment{proof}{{\bf Proof:}}{$\Box$}
\newtheorem{rem}{Remark}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}
\newtheorem{theorem}{Theorem}


\begin{document}

\begin{center}
{\bf \large Diophantine properties of linear recursive sequences II.} \\[2ex]
Attila Peth\H{o}\footnote{This paper was written when the author was a 
visiting professor at the Mathematical Institute of the Technical University 
of Graz, Austria.\\
Research partially supported by Hungarian National
Foundation for Scientific Research Grant No 16741 and 25157.} \\
Institut for Mathematics and Informatics\\
University of  Debrecen\\
H-4010 Debrecen, PO Box 12, Hungary\\
{\small e-mail: pethoe@math.klte.hu}
\date{\today}
\end{center}

\centerline{\it Dedicated to the 60th birthday of Professor \'Arp\'ad Varecza}

\bigskip

\noindent
{\small \it 2000 Mathematics Subject Classification: 11D61, 11D25}

\bigskip

\section{Introduction }

Let $G_n$ be a $k$-th ($k \ge 2$) order linear recursive sequence, in the
sequel LRS,  of integers
defined by initial terms $G_0,\dots,G_{k-1} \in \Z$ and by the relation
$$
G_{n+k} = A_1 G_{n+k-1}+ \dots + A_kG_n
$$
for $n \ge 0,$ where $A_1,\dots,A_k \in \Z, \; A_k \not= 0.$ We assume that
at least one of the initial terms of $G_n$ is non-zero. In the present
paper we continue our survey on results concerning the mixed exponential-polynomial
diophantine equation
\begin{equation} \label{1}
G_n = P(y),
\end{equation}
where $P(y) \in \Z[y]$ denotes a polynomial of degree $d \ge 2.$ In the first part 
\cite{P8} we concentrated on results proved by using elementary and algebraic tools.
Here we are dealing with applications of lower bounds for linear forms in logarithms 
of algebraic numbers. 

Most of the text of the paper is four years old. In 1996 I delivered an invited talk at the Seventh International Research Conference on Fibonacci Numbers and Their Applications. The edited version of the first part of that talk appeared in \cite{P8}, while the second part remains up to now unpublished. I extended this manuscript with some new results. 

Although the paper is a survey it includes new results too. You find an explicit bound for the exponent of perfect powers appearing in the classical Fibonacci and Lucas sequences. Another new result is Theorem \ref{Tr}, where we prove by the combination of effective and non-effective methods that, under certain condition, there exit only finitely many perfect powers in cubic recurrences. 


\section{Applications of lower bounds for linear forms in logarithms of algebraic numbers} \label{Baker}

The most powerful tools for the solution of equation (\ref{1}) are certainly lower bounds for linear forms in logarithms of algebraic numbers. One can prove not only general finiteness 
theorems, but combining with numerical diophantine approximation techniques one can completely 
solve single and even parametrized families of equations. In this section we collect some result
proved on this way. 

The first general lower bound for linear forms in logarithms of algebraic numbers was proved by A. Baker \cite{Ba1}. Since them several improvements and refinements appeared in the literature. It 
has a lot of applications. Analogous results were proved for linear forms in p-adic, in elliptic and in 
p-adic elliptic logarithms of algebraic numbers as well. Although they have also important applications in the theory of recurrences, see \cite{ShT}, we are dealing here only with the most classical case. For a collection of results proved by Baker's method and further references 
we refer to the monographs \cite{Ba2,ShT,Sm}.

Here we cite three recent results of this kind. All three are very sharp, but under certain circumstances they give different results (sometimes nothing), therefore it is worth to choose  
the best appropriate one in a concrete case. We need some further definition. 
Let the algebraic number $\beta$ be a zero of the irreducible polynomial
$p(y)=a_tx^t+ \dots +a_0 \in \Z[y]$, where $(a_t,\dots,a_0)=1$. Denote $\beta=\beta_1,\dots,\beta_t$ the zeros of $p(y)$. The absolute logarithmic height of
$\beta$ is defined by
\[
h(\beta)=\frac{1}{t}\log\left(\prod_{i=1}^t \max \{1,|\beta_i| \} \right).
\]

In the sequel let $\alpha_1,\dots,\alpha_m$ be non-zero algebraic numbers and $b_1,\dots , b_m$ rational integers. For $i=1,\dots,m$, let
$\log \alpha_i$ be a determination of the logarithm of $\alpha_i$ and 
\[
\Lambda =b_1 \log \alpha_1 + \dots + b_m \log \alpha_m.
\]
Assume further that $\Lambda \not= 0.$

The first theorem is due to Baker and W\"ustholz \cite{BW}.

\begin{theorem} \label{bw}
Let $D=[\Q(\alpha_1,\dots,\alpha_m):\Q]$ and $B= \max \{ |b_1|,\dots , |b_m|,e \}.$ Then
$$\log |\Lambda| \ge -18 (m+1)! m^{m+1} (32D)^{m+2} h(\alpha_1)\cdots
h(\alpha_m) \log B.$$
\end{theorem}

This theorem is very easy to apply, but it makes not possible for example to prove a bound for exponents for perfect powers in recursive sequences. 
For such purpose we shall apply the following result of Waldschmidt \cite{W}.

\begin{theorem} \label{wa}
Put 
\[
D=[\Q(\alpha_1,\dots,\alpha_m):\Q]  \quad \mbox{and} \quad 
g=[\R (\log \alpha_1,\dots,\log \alpha_m):\R].
\]
Let $h_1,\dots,h_m,E$ and $f$ be positive real numbers such that 
\[
\log h_i \geq h(\alpha_i), \quad (1\leq i \leq m), \quad h=\max\{h_1,\dots,
h_m\}
\]
and
\[
e\leq E \leq \min\left\{ h^D_1,\dots,h^D_m,\frac{mD}{f} \left(\sum^m_{i=1} 
\frac{|\log \alpha_i|}{\log h_i}\right)^{-1} \right\}.
\]
Assume that $b_m\not= 0$ and  put
\[
B=\max_{1 \leq j \leq m} \left\{ \frac{|b_m|}{\log h_j} + \frac{|b_j|}{\log 
h_m} \right\},
\]
\[
Z_0= \max \left\{ 7+3 \log m, \frac{g}{D} \log E, \log \left(\frac{D}
{\log E}\right) \right\}, \quad H_0=\max\{ 4mZ_0, \log B \}
\]
and
\[
U_0= \max \{ D^2 \log h,D^{m+2} H_0 Z_0 \log h_1 \cdots \log 
h_m(\log E)^{-m-1} \}.
\]
Then the linear form $\Lambda$ satisfies
\[
|\Lambda| \geq \exp \left\{ -1500g^{-m-2} 2^{2m} m^{3m+5} \left(1 + 
\frac{g}{f}\right)^m U_0 \right\}.
\]
\end{theorem}

In solving equations related to second order recurrences we often meet cases,
when only two algebraic numbers are involved, i.e. $m=2.$ Then there are even 
sharper lower bounds available. We cite here Corrollaire 1 of Laurent, Mignotte 
and Nesterenko \cite{LMN}. 

\begin{theorem} \label{lmn}
Let $\alpha_1, \alpha_2$ be multiplicatively independent algebraic numbers  
and $b_1, b_2$ be integers. Put $D=[ \Q(\alpha_1,\alpha_2):\Q ] / 
[\R(\alpha_1,\alpha_2):\R ]$ and
$$ \Lambda= b_1 \log \alpha_1-b_2 \log \alpha_2.$$

Let $h_1,h_2>1$ real numbers satisfying 
$$
\log h_i \ge \max \left\{ h(\alpha_i),\frac{|\log \alpha_i|}{D},\frac{1}{D} 
\right\}, \; i=1,2
$$
and put
$$
b= \frac{b_1}{D \log h_2} + \frac{b_2}{D \log h_1}.
$$
Then
\begin{eqnarray*}
\log | \Lambda| \ge -30.9 D^4 \left( \max \left \{ \log b, \frac{21}{D},\frac{1}{2}
\right\} \right)^2 \log h_1 \log h_2.
\end{eqnarray*}
\end{theorem}

In the applications of the above lower bounds the following simple lemmata are 
useful. For their proofs we refer to \cite{PW}.

\begin{lemma} \label{dew}
Let $a \in \R.$ If $0<a<1$ and $0<|x|<a$ then
$$
|\log(1+x)| < \frac{-\log(1-a)}{a}|x|. 
$$
\end{lemma}

\begin{lemma} \label{pew}
Let $a \ge 0, h \ge 1, b>(e^2/h)^h,$ and let $x \in \R, x>1$ satisfy
$$
 x \le a + b \log^hx.
$$
Then
$$
x < 2^h \left(a^{1/h} + b^{1/h} \log(h^hb)\right)^h.
$$ 
\end{lemma}

%!!
\subsection{Perfect powers in LRS. Bounding the exponents.}

Let $G_n$ be a LRS with characteristic polynomial 
$C_G(y)=y^k-A_1 y^{k-1}-\dots -A_k.$ 
Let $\alpha_1,\dots, \alpha_h$ 
denote the distinct zeros of $C_G$ with 
multiplicities $m_1,\dots, m_h$ respectively. Then there exist polynomials $g_i(y) \in \Q(\alpha_1,\dots, \alpha_h)[y]$ of 
degree less than $m_i, \; i=1,\dots , h,$ such that
\begin{equation} \label{2}
G_n = g_1(n)\alpha_1^n+\dots+g_h(n)\alpha_h^n
\end{equation}
holds for any integer $n\ge 0.$ 

In this section we are dealing with the solutions $n,y,q \in \Z$ of the equation
\begin{equation} \label{12u}
G_n = y^q.
\end{equation} 
The letters $c_1,c_2,\dots$ will denote effectively computable constants depending
only on the initial terms and on the coefficients of the characteristic polynomial
of $G_n.$ 
 
For binary recurrences Shorey and Stewart \cite{ShSt1} and independently the
author of the present notes
\cite{P1} proved that $\max \{ n,|y|,q\} < c_1$. We come back to this result in 
section \ref{bin}. For higher order recurrences much less is known. There are 
results only in that case, when $G_n$ has a dominating characteristic zero. Under
this assumption Shorey and Stewart \cite{ShSt1} proved 
that $q<c_2$ provided $|y|>1.$ 
Moreover Nemes and Peth\H{o} \cite{NP1} showed that if $T(y)\in \Z[y]$ is a fixed 
polynomial, then $q<c_3$ holds for any solutions $n,y,q \in \Z$ of the equation
\begin{equation} \label{41}
G_n = y^q +T(y)
\end{equation}
as well, provided $|y|>1.$ The constant $c_3$ depends naturally on the coefficients 
of $T(y)$ too. Recently Kiss \cite{K3} succeeded to refine in some cases this result. He also proved \cite{K1} the lower bound $|G_n - y^q|>e^{cn},$ provided $\alpha_1>|\alpha_2|>|\alpha_i|, i>2.$  Shorey and Stewart \cite{ShSt2} established under the same assumption that there exist only finitely many solution $n,y,q$ with $n\ge 0, |y|>1$ and
$$
q > \max \left \{ \frac{k \log \alpha_1}{\log (\alpha_1/ \max\{1,|\alpha_2| \})}, 
[\Q(\alpha_1):\Q]+\deg T \right \}.
$$ 
We also mention that this result is not effective, we do not know any upper bound for $\max\{n,|y| \}.$ 
A collection of the most general results of this kind you find in \cite{ShT}.

Remark that for fixed $q$ the last equation may have infinitely
many integer solution. Indeed, let $H_n$ be a LRS and $T(y) \in \Z[y]$ a polynomial.
Then $G_n=T(H_n)$ is an LRS as well and the equation 
\begin{equation} \label{GnT}
G_n=T(y)
\end{equation}
has infinitely many
solutions. It is widely believed that the converse is also true, i.e. the equation 
$G_n=T(y)$ has infinitely many solution only when $G_n$ has a subsequence of the form $T(H_n),$ with an LRS $H_n.$ Positive answer for this problem was known until very recently again only for binary recurrences and only in the case when $|A_2|=1$. (See 
\cite{NP2,P4}.)  The situation changed with the papers \cite{CZ1} and \cite{CZ2}. In that papers Corvaja and Zannier proved similar results under quite general conditions. Let $G_n$ be an LRS such that all of the zeros of its characteristic polynomial are simple and such that $\alpha_1$ is dominating, i.e. $1 \not= |\alpha_1 | > |\alpha_i|, i=2,\dots ,k.$ Let $T(y)\in \Z[y]$ be a monic polynomial. If the equation (\ref{GnT}) has infinitely many 
$n,y \in \Z, n \ge 0$ solutions then there exists an LRS $H_n$ of algebraic numbers and an arithmetical progression $P$ such that $G_n=T(H_n)$ holds for all $n \in P.$ Especially, let $q\ge 2$ be fixed and let $G_n$ be a $q$-th power for infinitely many $n$, then $G_n=H_n^q$ holds for all $n$ belonging to an arithmetical progression. In fact the theorem of Corvaja and Zannier is much more general. 

In the above mentioned papers the dependence on the constants on the parameters 
was never examined. In this section, following essentialy the earlier line, I intend
to prove an explicit upper bound for the exponents of possible perfect powers 
in $G_n.$  

\begin{theorem} \label{pow}
Let $G_n$ be a LRS such that all of the zeros of its 
characteristic polynomial are simple and 
$\alpha:=\alpha_1> |\alpha_2| \ge |\alpha_i|,  i=3,\dots,k.$ 
Put 
$$
\delta:=\frac{\log|\alpha_2|}{ \log \alpha}, \quad \quad c_1:=  \sum_{i=2}^{k} 
\frac{|g_i|}{|g_1|}, \quad \quad  a_1=\exp\{\max\{h(g_1),e\} \}
$$ 
and 
\begin{eqnarray*}
c_2&:=&\max \left \{\frac{1}{\log 2}\left( \frac{\log(4c_1)}{1-\delta}+ 
\log(c_1+1) + \log|g_1|\right), \frac{\log \alpha}{2}(k!)^{14},
3\log\left( \frac{5|g_1|}{4} \right) + \right. \\
& &\frac{2 \log (1.15 c_1)}{1-\delta} + 
\left. \frac{1}{1-\delta }4\cdot 10^{13} (k!)^7 \log a_1 
\log \alpha \left( 217 \log(k!) \log\log a_1 - \log(1-\delta) \right) \right \} .
\end{eqnarray*} 
Assume that 
$n,y,q \in \Z$ is a solution of (\ref{12u}) such that $|y|> 1.$ Then 
$$
q < c_2.
$$
\end{theorem}

\begin{proof}
Let $\K=\Q(\alpha_1,\dots,\alpha_k).$ First we remark, that as the zeros of 
$C_G(y)$ are simple, the polynomials $g_i(y)\in \K[y], i=1,\dots, k$ are 
actualy constants, thus the definition of $a_1,c_1$ and $c_2$ is correct.

Let $n,y,q \in \Z$ be a solution of (\ref{12u}) such that $|y|> 1$ and 
$$
q \ge \frac{1}{\log 2} \left( \frac{\log(4c_1)}{1-\delta}+ \log(c_1+1) + 
\log|g_1|\right).
$$ 
Then
$$
|g_1|(c_1 +1) (4c_1)^{1/(1-\delta)} \le 2^q \le |y|^q <|g_1|(c_1 +1) \alpha^n,
$$
thus $\alpha^{n(1-\delta)} > 4 c_1.$ We now obtain the following important 
inequality
$$
\left | \frac{|y|^q}{|g_1|\alpha^n} -1 \right| \le \sum_{i=2}^{k} \left | 
\frac{g_i}{g_1} \right|
\left | \frac{\alpha_i}{\alpha} \right|^n \le c_1 \alpha^{-n(1-\delta)} < 
\frac{1}{4}.
$$
From this we obtain on the one hand
\begin{equation} \label{12b}
\frac{q}{\log \alpha} - \frac{\log(5|g_1|/4)}{\log \alpha \log |y|} < \frac{n}{\log |y|}<
\frac{q}{\log \alpha} - \frac{\log(3|g_1|/4)}{\log \alpha \log |y|}
\end{equation}
and 
\begin{equation} \label{12}
|\Lambda_1|:=|\log|g_1| + n \log \alpha - q \log|y| | < 
1.15 \cdot c_1 \alpha^{-n(1-\delta)} 
%= \exp \{ -n(1-\delta)\log \alpha + \log (1.15 c_1) \}
\end{equation}
on the other hand. The last inequality follows from Lemma \ref{dew}. The expression 
staying on the left hand side of (\ref{12}) is a linear form in logarithms of 
algebraic numbers and we have just proved a sharp upper bound for it. 

A useful lower bound can be derived in this case only from Theorem \ref{wa}. We have in the 
present case $m=3, g=1, b_1=1,b_2=n,b_3=q$ and $D \le k!,$ but actually we need only an upper 
bound for the degree of $\K$ over $\Q,$ therefore we may take $D=k!.$ We choose $E=e, f=1,
h_1 = a_1, \log h_2= k \log \alpha$  and $h_3 = |y|.$ These parameters satisfy the assumptions of Theorem \ref{wa}. 

Now we are able to compute $B.$ Indeed, we have obviously
 \begin{eqnarray*}
B &=& \max \left \{ \frac{q}{\log a_1} + \frac{1}{\log |y|}, 
\frac{q}{k \log \alpha}+ \frac{n}{\log |y|} \right \}  \\
 &=& \frac{q}{k \log \alpha}+ \frac{n}{\log |y|}  < 
\frac{2q}{\log \alpha} - \frac{\log(3|g_1|/4)}{\log \alpha \log |y|}.
 \end{eqnarray*}
 Further 
$$Z_0= \max \{ 7+3 \log 3 , \log k! \}\le 14 \log(k!).
$$

Now we have to distinguish two cases according to the value of $H_0.$ Assume first that
$B \le (k!)^{14}.$ Then $H_0=4mZ_0=168\log(k!),$ which yields
$$
U_0 < 2352 (k!)^7 \log(k!) \log a_1 \log \alpha \log|y|,
$$
hence
$$
\log |\Lambda_1| > -8.64 \cdot 10^{15} (k!)^7 \log(k!) \log a_1 \log \alpha \log|y|.
$$
Comparing this inequality with (\ref{12}), dividing by $(1-\delta) \log|y|$ and using (\ref{12b}) 
we obtain the upper bound 
$$
q < \frac{1}{1-\delta}8.64 \cdot 10^{15} (k!)^7 \log(k!) \log a_1 \log \alpha +
\frac{\log(1.15c_1)}{(1-\delta)\log 2},
$$
which is obviously smaller than $c_2$. Hence the assertion is proved in this case.

\medskip

Now we turn to the other case $B > (k!)^{14},$  when $H_0= \log B.$ We have in this case
$$
U_0 < (k!)^7  \log a_1 \log \alpha \log|y| \log B,
$$
which yields
$$
\log |\Lambda_1| > -3.68 \cdot 10^{12} (k!)^7 \log a_1 \log \alpha  \log|y| \log B.
 $$
Comparing this inequality with (\ref{12}), dividing by $(1-\delta) \log \alpha \log|y|$ and using (\ref{12b}) we obtain the inequality
%\begin{eqnarray*}
$$
X < 
\frac{1}{1-\delta}7.36 \cdot 10^{12} (k!)^7  \log a_1 \log X +
\frac{2 \log(1.15 c_1)}{(1-\delta)\log \alpha} +
\frac{\log(25|g_1|/12)}{\log \alpha \log |y|},
$$
%\end{eqnarray*}
where
$$
X = \frac{2q}{\log \alpha} - \frac{3|g_1|/4}{\log \alpha \log |y|}.
$$
Application of Lemma \ref{pew} yields the upper bound
\begin{eqnarray*}
X &<& \frac{4 \log(1.15 c_1)}{(1-\delta)\log \alpha}+
\frac{1}{1-\delta} 14.72 \cdot 10^{12} (k!)^7  \log a_1 \cdot \\
& & \left( 217 \log(k!) \log \log a_1 -\log(1-\delta)\right) 
+ \frac{2 \log(25|g_1|/12)}{\log \alpha \log |y|},
\end{eqnarray*}
which implies 
\begin{eqnarray*}
q &<& \frac{2 \log(1.15 c_1)}{1-\delta}+
\frac{1}{1-\delta}7.36 \cdot 10^{12} (k!)^7  \log a_1 \log \alpha \cdot \\
& & \left( 217 \log(k!) \log \log a_1 -\log(1-\delta)\right) +
3 \log(5|g_1|/4).
\end{eqnarray*}
The number on the right hand side is again smaller than $c_2,$  hence the theorem is
proved.
\end{proof}

\bigskip

To have an impression how large is $c_2$ we computed it for the Fibonacci sequence.

\begin{cor} If $F_n=y^q$ for some $n,y,q \in \Z$ with $|y|,q>1$ then
$$
q< 5.1 \cdot 10^{17}.
$$
\end{cor}

\begin{proof}
It is well known that 
$$
F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right].
$$
Thus the conditions of Theorem \ref{pow} are fulfilled and we have to compute $c_2$ with the following values of the parameters: $ k=2,\alpha=(1+\sqrt{5})/2, \delta=-1, c_1=1, a_1=e^e$
and $g_1=1/\sqrt{5},$ which yields the upper bound $5.1 \cdot 10^{17}$ for $q.$
\end{proof}


The bound for the exponent of possible perfect powers in the Fibonacci sequence 
is fairly large. Remark that applying Theorem \ref{wa} directly to the linear form (\ref{12}) 
coming from the Fibonacci sequence we could be able to improve slightly the bound for $q$, but
even this bound would not be smaller then $10^{14}.$  The reason is the dependence of  Waldschmidt's bound on the parameter $m.$ 

If, however $g_1=1,$ which appears for example in
the Lucas sequence, we have only two terms in  (\ref{12}) and may use Theorem \ref{lmn}, which
yields a much better bound. We do this more generaly for the sequences $V_n(A_1,A_2)$ which is defined by $V_0(A_1,A_2)=2,
V_1(A_1,A_2)=A_1$ and by the recursion 
$V_{n+2}(A_1,A_2)=A_1 V_{n+1}(A_1,A_2) + A_2 V_n(A_1,A_2)$
for $n\ge 0.$

\begin{theorem} \label{luc}
Let $A_1,A_2$ be integers such that $A_1>0,|A_2|=1$ and $D:=A_1^2+4A_2>0.$ Let
further $\alpha=(A_1 + \sqrt{D})/2.$ If the integers $n,y,q$ with $|y|,q>1$ solve 
the equation 
\begin{equation} \label{31}
V_n(A_1,A_2) = y^q
 \end{equation}
then 
$$
q< 55125 \log \alpha.
$$
Moreover, if $(A_1,A_2)=(1,-1)$ or $(2,-1)$ then $q< 13222.$
\end{theorem}

\begin{proof}
Putting $\beta=(A_1 - \sqrt{D})/2,$ then $V_n=\alpha^n+\beta^n$ holds for all $n.$
Assume that the integers $n,y,q$ with $|y|,q>1$ are solutions of (\ref{31}).
As the assertion of the theorem trivialy holds for $n\le 10,$ we assume $n>10$ in 
the sequel and  obtain
$$
\left| \frac{y^q}{\alpha^n} -1 \right| = \alpha^{-2n} < 0.01.
$$
This implies the inequalities
\begin{eqnarray*} 
q \log y - 0.01 < n \log \alpha &<& q \log y + 0.01 \label{32}\\
|\Lambda|:=|q \log y -n \log \alpha| &<& 1.1 \alpha^{-2n}. \label{33}
\end{eqnarray*}
We are ready to apply Theorem \ref{lmn} to get a lower bound for $|\Lambda|.$

Set $b_1=q,b_2=n,h_1=y$ and 
$$
h_2= \left\{ \begin{array}{rll}
(\log \alpha)/2 &\mbox{, if }& A_1 \ge 3 \\
1/2 &\mbox{, if }& A_2=1 \; \mbox{and}\; A_1=1,2.
\end{array} \right. 
$$
Then we have in the general case
$$
b=\frac{q}{\log \alpha}+\frac{n}{2 \log y} \le \frac{3q}{2\log \alpha} + 0.15
$$
and in the special cases $b<2.04 q + 0.015.$ 

Assuming $q> 55000 \log \alpha$ ($q>13000$ in the special cases) we have
$$
\max \left\{ \log b, 10.5,0.5 \right\} = \log b.
$$ 
In the rest we are dealing with the general case, the proof for the special cases is
completely similar. Now Theorem \ref{lmn} yields
$$
\log |\Lambda| \ge 247.2 \log^2 \left( \frac{1.725 q}{\log \alpha}+0.018 \right)
\log y \log \alpha.
$$
Comparing this with the upper bound we obtain
$$
2q \log y -0.1 < 247.2 \log^2 \left( \frac{1.725 q}{\log \alpha}+0.018 \right)
\log y \log \alpha.
$$
 Dividing this inequality by $2 \log y \log \alpha/ 1.725$ and putting 
$X:= \displaystyle  \frac{1.725 q}{\log \alpha}+0.018$ we have
$$
X < 426.5 \log^2 X + 0.24,
$$
which implies $X< 95100$ by Lemma \ref{dew} and the assertion follows from the
definition of $X.$ 
\end{proof}

\bigskip

Even the bound $13222$ is too large to try to compute with known techniques all perfect
powers in the Lucas sequence. The only recursive sequence for which we know all perfect
powers is the Pell sequence $U_n(2,1).$ Peth\H{o} \cite{P6} and independently Cohn \cite{Co} proved that the equation
$$
P_n = y^q
$$
has solutions only for $q=2$ and these are $(n,y)=(0,0),(1,1)$ and $(7,13).$ Peth\H{o} ruled out
the odd exponents by elementary means. For $q=2$ and $n$ odd  Wolfskill \cite{Wo} proved
that $n<469,$ and below this bound is very easy to find all squares. The statement for even index
squares follows from divisibility properties of the Pell numbers.
%!!!

\subsection{Perfect powers in high order recurrences} 

If $G_n$ is a LRS satisfying the conditions of Theorem \ref{pow} then there are
no non-trivial (from $0$ and $1$ different) $q$-th power in $G_n$ provided $q$ 
is large enough. You have seen, that this bound is usualy large. But this is 
not so bad, because the constants in the linear form bounds are continously 
improved and I expect in the future for a wide class of LRS at least such a good 
bound as for the Lucas sequence. 

Four years ago I continued with the following sentences: {\em Annoying is that we have generaly no information about small powers. The tribonacci
sequence defined in the Problem of \cite{P8} satisfies the condition of Theorem \ref{pow},
but we do not know how many squares, third powers, etc. appear in it. We are 
not able to prove even that their number is finite. 

Similarly, we know nothing about the squares or higher powers in the sequence
$(2^n-1)(3^n-1).$ This seems hard for squares and a bit easier for higher 
powers. } 

The situation changed considerably in the recent years. L. Szalay \cite{Sz} established all squares in the sequence $(2^n-1)(3^n-1).$ Hajdu and Szalay \cite{HSz} did the same for the sequences $(2^n-1)(6^n-1)$ and $(a^n-1)(a^{kn}-1).$  In both papers there are used only elementary methods.

Much more interesting are the results of Corvaja and Zannier \cite{CZ1} and \cite{CZ2}. They considered in \cite{CZ1} LRS with integer characteristic roots and proved: Let 
$$
G_n = g_1 a_1^n + \dots + g_k a_k^n,
$$
where $k \ge 2, g_1,\dots , g_k$ are non-zero algebraic numbers and $a_1>a_2>\dots > a_k>0$ are integers with $a_1,a_2$ coprime. Then for every integer $d\ge 2$ equation (\ref{12u}) has only finitely many solutions $n,y \in \N.$ Remark that they used in the proof W.M. Schmidt's \cite{Schm} celebrated subspace theorem, hence the result is not effective.

Combining this result with Theorem \ref{pow} one obtains under the same assumptions as above that there are only finitely many perfect powers in the sequence $G_n$. 

Moreover combining Theorem \ref{pow}  with Theorem 2 of \cite{CZ2} we are able to prove the following theorem.

\begin{theorem} \label{Tr}
Let $G_n$ be a third order LRS. Assume that the characteristic polynomial of $G_n$ is irreducible and has a dominating root. Then there are only finitely many perfect powers in $G_n$.
\end{theorem}

\begin{rem}
The tribonacci numbers are defined by the initial terms $T_0=T_1=0,T_2=1$ and by the recursion $T_{n+3}=T_{n+2}+T_{n+1}+T_n$ for $n\ge 0.$ In Part I \cite{P8} I asked whether $T_0=T_1=0, T_2=T_3=1, T_5=4, T_{10}=81, T_{16}=3136 = 56^2$ and $T_{18}=10609 = 103^2$ are the only perfect squares among the tribonacci numbers. It follows from Theorem \ref{Tr} that there are only finitely many perfect powers in $T_n$. This is a partial answer to my question. Remark that Theorem \ref{Tr} is not effective, hence we have presently no algorithm for computing all powers in the sequence $T_n$.
\end{rem}

\noindent
{\it Proof of Theorem \ref{Tr}.} The assumptions of Theorem \ref{pow} fulfill, hence if $G_n=y^q$ and $|y|>1$ then $q<c_2$ with an effectively computable constant $c_2.$  

In the rest of the proof let $2 \le q <c_2$ be fixed. Assume that (\ref{12u}) has for this $q$ infinitely many solutions in $n,y \in \N, y>1.$ Then there exist by \cite{CZ2} (Theorem 2) non-zero algebraic numbers $d_1, \dots ,d_r, \delta_1, \dots ,\delta_r$ such that 

\begin{equation} \label{*}
G_n = g_1 \alpha_1^n + g_2 \alpha_2^n + g_3\alpha_3^n = 
\left( d_1\delta_1^n + \dots + d_r\delta_r^n \right)^q 
\end{equation}
holds for all elements $n$ of an arithmetical progression $P.$ We may assume without loss of generality that $|\delta_1| \ge \dots \ge |\delta_r|$.

%\end{document}

There exist, by a theorem of van der Poorten and Schlickewei \cite{PSch}, for any $\varepsilon >0$ constants $c_4$ and $c_5(\varepsilon)$ such that 
$$
c_5(\varepsilon) |\delta_1|^{n(1-\varepsilon)} \le \left| \sum_{i=1}^r d_i \delta_i^n \right|
\le c_4 |\delta_1|^n
$$
holds for all $n > n(\varepsilon)$. On the other hand
$$
|g_1||\alpha_1|^n/2 \le |G_n| \le 2 |g_1||\alpha_1|^n
$$
is true, provided $n$ is large enough. 

Hence on one hand
$$
\left| \frac{\delta_1^q}{\alpha_1} \right|^n \ge   \frac{|g_1|}{2c_4^q}
$$
for all sufficiently large $n$, which implies
$$
|\alpha_1| \le |\delta_1|^q.
$$

On the other hand we have 
$$
\left( \frac{|\delta_1^q|^{1-\varepsilon }}{|\alpha_1|} \right)^n \ge   \frac{2|g_1|}{(c_5(\varepsilon ))^q}
$$
for any fixed $\varepsilon>0$ and all $n \ge n(\varepsilon).$ This implies
$$
|\alpha_1| \ge |\delta_1|^{q(1-\varepsilon)}
$$
for all $\varepsilon>0.$ The lower and upper bounds for $|\alpha_1|$ imply $|\delta_1| = |\alpha_1|^{1/q}$.
\medskip

Assume that $ |\delta_1| = \dots =|\delta_s| = |\alpha_1|^{1/q}>|\delta_{s+1}| \ge |\delta_r|.$ Define $D_1(n) = \sum_{i=1}^s d_i \delta_i^n$ and 
$D_2(n) = \sum_{i=s+1}^r d_i \delta_i^n$ and rewrite (\ref{*}) as
$$
g_1\alpha_1^n+g_2\alpha_2^n+g_3\alpha_3^n = 
(D_1(n) + D_2(n))^q = D_1(n)^q 
+\sum_{j=1}^q {q \choose j} D_1(n)^{q-j} D_2(n)^j.
$$
This implies
\begin{equation} \label{**}
g_1\alpha_1^n - D_1(n)^q = \sum_{j=1}^q {q \choose j} D_1(n)^{q-j} D_2(n)^j - g_2\alpha_2^n - g_3\alpha_3^n.
\end{equation}

There is staying on the left hand side a finite power sum. If it is non-zero then for any $\varepsilon>0$ its absolute value is bounded below by $c_6(\varepsilon) |\alpha_1|^{n(1-\varepsilon)}.$
In contrast the right hand side is obviously bounded above by 
$c_7 |\alpha_1|^{n(q-1)/q} < c_7 |\alpha_1|^{n(1-\eta)}$ with a fixed $\eta>0.$ This is a contradiction, hence
$$
g_1\alpha_1^n = D_1(n)^q,
$$
which can be written as
$$
g_1^{1/q}(\alpha_1^{1/q})^n - \sum_{i=1}^s d_i \delta_i^n = 0.
$$
This is an $S$-unit equation in the field $\Q(g_1^{1/q},\alpha_1^{1/q}, d_1, \dots, d_s, \delta_1, \dots ,\delta_s)$, which has infinitely many solutions in $n\in \N$. By the theorem
of Evertse \cite{Ev1} there exists a $1\le i \le s$ such that $ g_1^{1/q}(\alpha_1^{1/q})^n =
d_i\delta_i^n$ holds infinitely often. We may assume $i=1$ without loss of generality, i.e.
we have 
$$
g_1^{1/q}(\alpha_1^{1/q})^n = d_1\delta_1^n \quad \mbox{and} \quad 
\sum_{i=2}^s d_i \delta_i^n = 0
$$
for infinitely many $n\in \N.$

For such integers $n$ we obtain
\begin{equation} \label{***}
\sum_{j=1}^q {q \choose j} d_1^{q-j}\delta_1^{(q-j)n} D_2(n) ^j -g_2\alpha_2^n -g_3\alpha_3^n =0
\end{equation}
from equation (\ref{**}). As $\alpha_2/\alpha_3$ is not a root of unity the sum 
$ g_2\alpha_2^n +  g_3\alpha_3^n$ never vanish if $n$ is large enough, hence
$D_2(n) \not= 0$ for such $n$'s. The function
$ {q \choose j} d_1^{q-j}\delta_1^{(q-j)n} D_2(n) ^j $ is for fixed $n$ 
strictly decreasing in $j$, hence writing it as a sum of exponential functions it has at least $q$
summands such that no proper subsums of their sum vanishes for infinitely many $n$.
From these one can be equal to $g_2\alpha_2^n$ and an other equal to $g_3\alpha_3^n$,
hence if $q>2$ then (\ref{***}) cannot hold for infinitely many $n.$

Finally let $q=2.$ Then (\ref{***}) simplifies to
\begin{equation} \label{iv}
2d_1\delta_1^n \left(\sum_{i=2}^r d_i \delta_i^n\right) + 
\left(\sum_{i=2}^r d_i \delta_i^n\right) ^2 -g_2\alpha_2^n -g_3\alpha_3^n = 0.
\end{equation}
This equation has infinitely many solutions in $n$. As $\sum_{i=2}^r d_i \delta_i^n \not=0$
for all large enough $n$, there exists a minimal index $2\le i_0 \le r$ and $J \subseteq R =
\{2,\dots , r \}$ such that $i_0 \in J,$
$$
\sum_{j\in R\setminus J} d_j\delta_j^n = 0 \quad \mbox{and} \quad
\sum_{j\in J_1 \subseteq J} d_j\delta_j^n \not= 0 
$$
for infinitely many solutions of (\ref{iv}) and for all $\emptyset \not= J_1 \subseteq J.$ 
Therefore $|J|=1$ and
$$
2d_1\delta_1^nd_{i_0}\delta_{i_0}^n + d_{i_0}^2 \delta_{i_0}^2n -g_2\alpha_2^n -g_3\alpha_3^n = 0.
$$
Hence the system of equations
\begin{eqnarray*} 
2d_1\delta_1^nd_{i_0}\delta_{i_0}^n &=& g_2\alpha_2^n \\
d_{i_0}^2 \delta_{i_0}^2n  &=& g_3\alpha_3^n 
\end{eqnarray*} 
or the analogous system of equations, where the right hand sizes are interchanged, 
has infinitely many solutions in $n$. 

These implies $\delta_1\delta_{i_0} = \alpha_2 \zeta_2$ and 
$\delta_{i_0}^2 = \alpha_3 \zeta_3,$ with some roots of unity $\zeta_2, \zeta_3.$
We also have $\delta_1^2=\alpha_1\zeta_1$ with a root of unity $\zeta_1.$ These
three relations imply 
$$
 \frac{\alpha_2^2}{\alpha_1 \alpha_3} = \frac{\zeta_1 \zeta_3}{\zeta_2^2}.
$$
Using finally that $\alpha_1 \alpha_2 \alpha_3$ is an integer $A$, we conclude that
$\alpha_2^3 = A\zeta,$ where $\zeta$ is a root of unity. Taking conjugates we conclude that $|\alpha_1|= |\alpha_2|= |\alpha_3|$,
which contradicts the assumption that one of the roots is 
dominating. The Theorem is proved. \hfill $\Box$

\subsection{Perfect powers in second order recurrences} \label{bin}

For second order recurrences we can bound effectively not only the exponents of the perfect powers appearing in the sequence, but also the largest index for which a term of the sequence 
can be a perfect power. This was proved by Shorey and Stewart \cite{ShSt1}
and independently by me \cite{P1}.  

\begin{theorem}
Let $G_n$ be a non-degenerated second order LRS and $d\in \Z$. Then there exist 
effectively computable positive constants $c_1,c_2$ depending only on $G_0,
G_1,A_1,A_2$ and on $d$ such that if for the integers $n,y,q$ such that $q>1$ 
the equation
\begin{equation} \label{21a}
G_n = y^q
\end{equation}
holds, then:
\begin{itemize}
\item[(a)] If $|y|>1,$ then  $\max \{ |y|,n,q \} < c_1,$
\item[(b)] if $|y|\le 1,$ then  $n<c_2.$
\end{itemize}
\end{theorem}

\begin{proof}
We may assume by Theorem \ref{pow}, that if $|y|>1,$ then $q$ is bounded by an
effectively computable positive constants $c_3$ depending only on $G_0,
G_1,A_1,A_2$ and on $d$. Let fix $q$ such that $1 < q < c_3.$  

Write 
$$
G_n = g_1 \alpha_1^n + g_2 \alpha_2^n
$$
and let
$$
H_n= \frac{g_1 \alpha_1^n - g_2 \alpha_2^n}{\alpha_1 - \alpha_2}.
$$
It is easy to check that $H_n$ is also an LRS of integers, $G_n$ and $H_n$ have
the same characteristic polynomial and 
$$
G_n^2 - (\alpha_1 - \alpha_2)^2 H_n^2 = 4(\alpha_1 \alpha_2)^n.
$$
Remark that $(\alpha_1 - \alpha_2)^2=A_1^2+4A_2$ and $\alpha_1 \alpha_2=-A_2$ 
are integers. Let
$S$ be the set of all prime divisors of $ A_2$ and $n,y$ be a 
solution of (\ref{21a}) for our fixed $q$ with $|y|>1.$ There exist
integers $r,s$ such that $n=s(2q)+r$ and $0 \le r <2q.$  The rational numbers
$\displaystyle\frac{G_n}{(A_2)^{qs}}$ and $\displaystyle \frac{y}{s}$ are $S$-integral solutions of the hyperelliptic equation
$$
z^2 = (A_1^2+4A_2) u^{2q} + 4 (-A_2)^r.
$$
The polynomial staying on the right hand side of this equation has for all
$0 \le r <2q$ at least three simple zeros, hence it has only finitely many 
effectively computable S-integer solutions.  

As there exists only finitely many possibilities for $q$ and for $r$ the number 
of the hyperelliptic equations to be considered is finite, thus the number of
solutions is finite and effectively computable.


The rest of the proof is easy, you find details in \cite{P1,ShSt1} or in 
\cite{ShT}.
\end{proof}

\subsection{A method for determining squares in second order LRS}

The above proof is simple and is very well for theoretical purposes. Its drawback
is that it is hard to find power values in given LRS following its line, because 
we transform the problem to finitely many hyperelliptic equations and their
solution is not at all easy. 

Mignotte and Peth\H{o} \cite{MP2} proposed a more direct way to solve (\ref{21a}) in case
$q=2$ and $|A_2|=1.$ We present now their method in this special form. They 
remarked that the method can be generalized to arbitrary $A_2$ and for arbitrary
$q.$  

\bigskip

Let $G_n$ be a second order recursive sequence with $|A_2|=1, d\in \Z$ and 
consider the equation
$$
G_n = g_1 \alpha_1^n + g_2 \alpha_2^n = d y^2.
$$
As $|A_2|=1$ the numbers $\alpha_1, \alpha_2$ are real quadratic units.
Put $\K=\Q(\alpha_1)$. Let $\gamma'$ denotes the conjugate of $\gamma{\in}\K$. 
Then $\alpha_2={\alpha_1}'.$ We may assume without loss of generality that 
$\alpha_1>{|}{\alpha_2}{|}$. Adjusting our equation appropriately (changing
$g_1$ and $g_2$ with $\alpha_1g_1$ and $\alpha_2g_2$ respectively if n is odd;
multiplying the equation with the square free part of $g_2$ and with $-1$ if 
necessary) we see that it is enough to deal with the equation
\[
a\alpha_1^{2m}-b^2\alpha_2^{2m}=cy^2,
\]
where $a,b$ and $c{\in}\Z_{\K}$ and $m,y{\geq}0$ are integers.  
Our aim is to prove an upper bound for $m.$ 

Let $\L=\K(\sqrt{-c})$ and assume that $\L$ is a quadratic extension of
$\K$, i.e. $[\L:\Q]=4.$ Then our equation implies
\begin{equation}
\label{15}
N_{\L/\Q}(b\alpha_2^m+\sqrt{-c}y)=N_{\L/\Q}(a)=A,
\end{equation}
with an integer $A$. \\
Choose in $\Z_{\L},$ in the ring of integers of $\L,$ units $\eta_2,\dots,
\eta_r;$ $r=1,2$ or $3$ such that the
group $ {\bf U}$ generated by $\eta_1=\alpha,\eta_2,\dots,\eta_r$ has finite index in
the group of units of $\Z_{\L}$. There exists in $\Z_{\L}$ a maximal finite set
of, with respect to $ {\bf U}$, non--associated elements of norm $A$. This set
will be denoted by ${\bf A}$. Then there exist for all
$m,x{\in}\Z$ with (\ref{15}) a $\gamma{\in}{\bf A}$ and $\varepsilon{\in} {\bf U}$
such that
\begin{equation}
\label{16}
b\alpha_2^m+\sqrt{-c}y=\gamma \varepsilon.
\end{equation}
Let order the conjugates $\L^{(i)},i=1,2,3,4$ of $\L$ according the following
ordering of the conjugates of
$\sqrt{-c}:\sqrt{-c},-\sqrt{-c},\sqrt{-c'},-\sqrt{-c'}.$  Let $R$ denote the
regulator of ${\bf U},$ i.e. the absolute 
value of the determinant of the matrix $(\log|\eta_i^{(j)}|)_{1\le i,j \le r}$ 
 and finally, for $\delta \in \Z_{\K}$  let 
$$
\overline{|\delta|}:= \max \{ |\delta^{(i)}, i=1, \dots , 4\}.
$$
It is easy to see that if $m>m_0$ then
\begin{equation}
\label{17a}
\frac{1}{2} \frac{\sqrt{| a |}}{| \gamma^{(i)} |} \alpha_1^m <
| \varepsilon^{(i)} | < \frac{2\sqrt{| a |}}{| \gamma^{(i)}|} \alpha_1^m
\end{equation}
for $i=1,2$; and if $b'>0$, which we may assume without loss of generality, then
\begin{equation}
\label{17b}
\frac{b'}{2|\gamma^{(3)}|} \alpha_1^m < | \varepsilon^{(3)} | < 2
\frac{b'}{| \gamma^{(3)} |} \alpha_1^m
\end{equation}
and
\begin{equation}
\label{17c}
\frac{|a'|}{2b'|\gamma^{(4)}|}  \alpha_1^{-3m} < | \varepsilon^{(4)} | <
\frac{2|a'|}{b'|\gamma^{(4)}|} \alpha_1^{-3m}
\end{equation}
hold. We remark that if $b'<0$ then only the role of $\varepsilon^{(3)}$
and $\varepsilon^{(4)}$ changes. 

\medskip

The last inequalities imply that {\it if $c'>0$ then (\ref{15}) has only 
finitely many solutions and they are very easy to compute.} In fact $\varepsilon^{(3)}$ and
$\varepsilon^{(4)}$ are in this case conjugate complex numbers, hence
\[
\frac{b'}{2| \gamma^{(3)} |} \alpha_1^m < | \varepsilon^{(3)} | =
| \varepsilon^{(4)} | < \frac{2|a'|}{b'|\gamma^{(4)}|} \alpha_1^{-3m},
\]
i.e $m<\displaystyle\frac{1}{4} \log \left|\displaystyle\frac{4a'\gamma^{(3)}}
{b^{'2}\gamma^{(4)}} \right|.$ \\[1ex]
The situation is more interesting when $c'<0.$ Then $\varepsilon^{(3)}$ and
$\varepsilon^{(4)}$ are real numbers and we will use estimations on linear forms
in logarithms of algebraic numbers to establish an upper bound for $m$. 
\bigskip

{\bf Let first $c>0$} (and $c'<0$). Then $\L$ has two nonreal and two real
conjugates, and there exist $u_1,u_2 \in \Z$ with $\varepsilon= \eta^{u_1}_1
\eta^{u_2}_2.$
The estimations (\ref{17a}) with $i=2$ and (\ref{17b}) yield
\[
| u_1 | < \frac{2m \log\alpha_1 | \log | \eta^{(3)}_2 |
-\log | \eta^{(2)}_2 ||}{R} +c_1
\]
and
\[ | u_2 | < \frac{4m\log^2\alpha_1}{R} +c_1, \]
where 
\[
c_1=2\log\left(3\overline{|a|} \overline{|b^2|} \overline{\left| \frac{1}{\gamma}
\right|} \right)\max \{\log\alpha_1,\log\overline{|\eta_2|} \}/ R.
\]
We have 
$$\gamma^{(1)} \varepsilon^{(1)}+\gamma^{(2)}\varepsilon^{(2)}=2b\alpha_2^m,
$$
hence
\[
\left|1+\frac{\gamma^{(2)}}{\gamma^{(1)}}\left(\frac{\eta^{(2)}_2}{\eta^{(1)}_2}
\right)^{u_2} \right| < \frac{4b}{\sqrt{|a|}} \alpha_1^{-2m}.
\]
If $m>m_0$, then $\displaystyle\frac{4b}{\sqrt{|a|}}\alpha_1^{-2m} <
\displaystyle \frac{1}{2}$ and so
\[
| \Lambda_1 | = \left| \log\left(-\frac{\gamma^{(2)}}{\gamma^{(1)}}\right)+u_2
\log\left(\frac{\eta^{(2)}_2}{\eta^{(1)}_2}\right)+u_0\pi \right| < \frac{4.1
| b |}{\sqrt{| a |}}\alpha_1^{-2m},
\]
where $u_0{\in}\Z$ and we take the principal value of the complex logarithm function, i.e. $-\pi 
\leq \log(z) \leq \pi$ for every $z \in \C.$ The
last inequality yields $| u_0 | < | u_2 | +2.$

As the field $\Q(\gamma^{(2)}/ \gamma^{(1)}, \eta^{(2)}_2/ \eta^{(1)}_2, \sqrt{-1})$ is
obviously a subfield of $\Q(\sqrt{-c},\sqrt{-c'}\sqrt{-1}),$ which is of degree at most $16$
over $\Q$ we can set $D=16$ and $B=|u_2|+2$ in Theorem \ref{bw} which yields the lower bound
\[
| \Lambda_1 | > \exp\left\{-1.25\cdot10^{18}h\left(\frac{\gamma^{(2)}}
{\gamma^{(1)}}\right)
h\left(\frac{\eta^{(2)}_2}{\eta^{(1)}_2}\right) \log(|u_2|+2) \right \}.
\]
Comparing the lower and upper bounds for $| \Lambda_1 |$ we conclude
\begin{equation}
\label{20}
2m\log\alpha_1 -\log\frac{4.1|b|}{\sqrt{|a|}}< 1.25\cdot10^{18}
h\left(\frac{\gamma^{(2)}}{\gamma^{(1)}}\right)h\left(\frac{\eta^{(2)}_2}
{\eta^{(1)}_2}\right) \log\left(\frac{4m\log^2\alpha}{R} +c_1 +8\right).
\end{equation}
This inequality yields an upper bound for $m$, which we shall only compute
knowing the actual values of the occouring parameters. 

\bigskip

{\bf Let now $c<0$} (and $c'<0$). Then all conjugates of $\L$ are real and there
exist $u_1,u_2,u_3 \in \Z$ with $\varepsilon = \eta^{u_1}_1
\eta^{u_2}_2\eta^{u_3}_3.$ We recall $\eta_1=\alpha_1.$ The estimations
(\ref{17a}) with $i=1,2$ and (\ref{17b}) yield
\[
| u_i | < \frac{4m\log^2\alpha_1 \log h}{R}+c_2, \ i=2,3,
\]
where
$$c_2=3\sqrt3 \log\left( 3\overline{|a|} \overline{|b^2|} 
\overline{| 1/\gamma}\right)
\log\alpha_1 \log\overline{|\eta_2|} \log \overline{|\eta_3|}/R$$ 
and
$h=\max\{\overline{|\eta_2|},\overline{|\eta_3|}\}.$ 

Similarly to the above case, but working with real instead of complex
logarithms we get
\[
| \Lambda_2 | =\left| \log \left| \frac{\gamma^{(2)}}{\gamma^{(1)}} \right|
+u_2 \log \left| \frac{\eta^{(2)}_2}{\eta^{(1)}_2} \right| + u_3 \log \left|
\frac{\eta^{(2)}_3}{\eta^{(1)}_3}\right|\right| < \frac{5.6|b|}
{\sqrt{| a |}} \alpha_1^{-2m}.
\]
The parameters in the application of Theorem \ref{bw} are the same as
earlier except that $D=8$ and 
 $B=\max\{| u_2 |,|u_3|\}.$  Hence Theorem \ref{bw} implies
\begin{equation}
\label{21}
2m\log\alpha_1-\log\frac{5.6|b|}{\sqrt{| a |}} < 3.87 \cdot 10^{16} h\left(\displaystyle
\frac{\gamma^{(2)}}{\gamma^{(1)}}\right)h\left(\displaystyle\frac{\eta^{(2)}_2}
{\eta^{(1)}_2}\right)h\left(\displaystyle\frac{\eta^{(2)}_3}
{\eta^{(1)}_3}\right) \log\left(\frac{4m\log^2 \alpha_1 \log h}{R} +
c_2\right).
\end{equation}
 
We again do not express an upper bound for $m$ explicitely, but rather show 
through an example how to use inequalities (\ref{20}) and (\ref{21}).

\bigskip

{\bf Example} Let $G_0=0, G_1=10$ and $G_{n+2}=10 G_{n+1}-G_n$ and consider the equation $G_{2m+1}= \Box.$ It is easy to see, that if we are
able to solve this equation then we can solve $G_n=\Box$ too. (See \cite{MP2}.) 

To solve the equation $G_{2m+1}= \Box$ we intend to apply the method described above. First we compute the necessary initial data. 
We have  
$\alpha_1 = 5+2\sqrt6,$ $\alpha_2=5-2\sqrt6$ and $ c=-12+5\sqrt{6} ,$
thus our equation has the form 
$$\alpha_1^{2m}-\alpha_2^2\alpha_2^{2m} = 4\alpha_2\sqrt{6}w^2=4(5\sqrt{6}-12)w^2.$$
It is easy to see that it has only one solution $(m,w)=(0,1)$ in the range 
$ 0 \le m \le 10 .$ If $m>10$ then (\ref{17a}) is obviously true. Thus we may 
assume in the sequel $m>10.$

The algebraic number field $\L=\Q(\sqrt{6},\sqrt{12-5\sqrt{6}}),$ has two real 
and two non-real conjugates. The units $\alpha_1$ and $\eta_2=5-2\sqrt{12-5\sqrt{6}}
-2 \sqrt{6}$ are fundamental units in $\Z_{\L},$ hence its regulator is 
$R = 6.83836$ and we get 
$$ |u_2| < 3.07398 m + 8.95847. $$

As $\gamma=1$ there are only two summands in $\Lambda_1,$ actually it has the 
form
\begin{equation} \label{20a}
\Lambda_1=\left| u_2 \log \left( \frac {5-2\sqrt{6}+2\sqrt{12-5\sqrt{6}}} 
{5-2\sqrt{6}-2\sqrt{12-5\sqrt{6}}} \right) +u_0 \pi \right| < 
0.042 \alpha_1^{-2m}.
\end{equation}
As we proved, there are generaly three logarithms in $\Lambda_1,$ but in the 
actual example we have only two, therefore in the, to (14) analogous inequality
we get a much better constant. More precisely we have
$$4.58486 m + 3.17387 < 6.81595 \cdot 10^{11} \log(12.4 m + 40), $$
which implies $ m < 5 \cdot 10^{12} $ and $|u_2| < 1.55 \cdot 10^{13}.$
Dividing the inequality for $\Lambda_1$ by $u_2 \pi$ we see that, as $m>10$, 
$u_0/u_2$ is a convergent of 
$$\log\left(\frac{\eta_2^{(2)}}{\eta_2^{(1)}}\right)/\pi= \delta=
 .93557845273700309088141600367180617252445255312155... $$

The denominator of the 26-th convergent of $\delta$, 
$\displaystyle\frac{ 51706546491839}{ 55266927472061},$ is larger than $10^{14},$ hence 
by the well known extremality property of the convergents of real numbers we obtain
$$|u_0-u_2\delta| \ge | 51706546491839 -  55266927472061 \cdot \delta|>
 0.16132\cdot10^{-13}.$$ 
Comparing this inequality with (\ref{20a}) we obtain
$$
0.16132\cdot10^{-13}< 0.0134 \alpha_1^{-2m},
$$
which implies $m \le 5.$ Thus our equation has only
the trivial solution $(m,w)=(0,1).$ 

\bigskip

\noindent
{\bf Aknowledgement.} The author thanks very much for the carefull work of
the referee.

\begin{thebibliography}{99}

\bibitem[Ba1]{Ba1}
{\sc A. Baker,} {\em Linear forms in the logarithms of algebraic numbers,} Mathematika
{\bf  13} (1966),  204--216.
\bibitem[Ba2]{Ba2}
{\sc A. Baker,} {\em Transcendental Number Theory,} Cambridge Univ. Press, 1975.
\bibitem[BW]{BW}
{\sc A. Baker} and {\sc G. W\"ustholz}, {\em Linear forms and
group varieties,} J. reine und angew. Math. {\bf 442} (1993), 19--62.
\bibitem[Co]{Co} 
{\sc J.H.E. Cohn}, {\em Perfect Pell powers}, 
Glasgow Math. J. {\bf 38} (1996), 19--20. 
\bibitem[CZ1]{CZ1} 
{\sc P. Corvaja} and {\sc U. Zannier}, {\em Diophantine equations with power sums and universal Hilbert sets}, Indag Math., N.S. {\bf 9} (1998), 317-332.
\bibitem[CZ2]{CZ2} 
{\sc P. Corvaja} and {\sc U. Zannier}, {\em Some new applications of the subspace theorem},
manuscript.
\bibitem[Ev1]{Ev1}
{\sc J.H. Evertse,} {\em On sums of S-units and linear
recurrences,} Comp. Math. {\bf 53} (1984), 225-244.
\bibitem[HSz]{HSz}
{\sc L. Hajdu} and {\sc L. Szalay}, {\em On the diophantine equations $(2^n-1)(6^n-1)=x^2$ and $(a^n-1)(a^{kn}-1)=x^2$,} Periodica Math. Hungar., to appear.
\bibitem[K1]{K1}
{\sc  P. Kiss,} {\em On common terms of linear recurrences}, Acta Math. Acad. 
Sci. Hungar. {\bf 40} (1982) 119-123.
\bibitem[K2]{K2}
{\sc  P. Kiss,} {\em Pure powers and power classes in recurrence sequences}, 
Math. Slovaca, {\bf 44} (1994) 525-529.
\bibitem[K3]{K3}
{\sc  P. Kiss,} {\em Note on a result of I. Nemes and A. Peth\H{o} 
concerning polynomial values in linear recurrences}, Publ. Math.
Debrecen {\bf 56 } (2000), 451--455. 
\bibitem[LMN]{LMN} 
 {\sc M. Laurent, M. Mignotte} et {\sc Y. Nesterenko},
{\em Formes lin\'eaires en deux logarithmes et d\'eterminants
d'interpolation}, J. Number Theory, {\bf 55} (1995), 285--321.
\bibitem[MP1]{MP1}
{\sc M. Mignotte} and {\sc A. Peth\H{o},} {\em Sur les carr\'es dans certaines 
suites de Lucas,} Journal de Th\'eorie Nombres de Bordeaux, {\bf 5} (1993), 
333-341.
\bibitem[MP2]{MP2}
{\sc M. Mignotte} and {\sc A. Peth\H{o},} {\em On the system of diophantine 
equations $x^2-6y^2=-5$ and $x=2z^2-1$,} Math. Scandinavica, {\bf 76} (1995), 
50--60.
\bibitem[MT]{MT}
{\sc M. Mignotte} and {\sc N. Tzanakis,} {\em Arithmetical study of recurrence 
sequences}, Acta Arith., {\bf 57} (1991). 357-364.
\bibitem[Mo]{Mo} 
{\sc L.J. Mordell,} {\em Diophantine Equations}, Academic Press, 1969.
\bibitem[N]{N}
{\sc I. Nemes,} {\em On the solution of the diophantine equation $G_n=P(x)$ with
sieve method}, in Computational Number Theory, Walter de Gruyter, Berlin-New 
York, 1991, pp. 303-311.
\bibitem[NP1]{NP1}
{\sc I. Nemes} and {\sc A. Peth\H{o},} {\em Polynomial values in linear 
recurrences I.}, Publ. Math. Debrecen, {\bf 31} (1984), 229-233. 
\bibitem[NP2]{NP2}
{\sc I. Nemes} and {\sc A. Peth\H{o},} {\em Polynomial values in linear 
recurrences II.,} J. Number Theory, {\bf 24} (1986), 47-53. 
\bibitem[P1]{P1} 
{\sc A. Peth\H{o},} {\em Perfect powers  in second order linear recurrences,} 
J. Number Theory, {\bf 15} (1982), 5-13.
\bibitem[P2]{P2} 
{\sc A. Peth\H{o},} {\em Full cubes  in the Fibonacci sequence,} Publ.  Math. 
Debrecen, {\bf 30} (1983), 117-127. 
\bibitem[P3]{P3} 
{\sc A. Peth\H{o},} {\em  Perfect powers in second order recurrences,} 
in: {\em Topics in Classical Number Theory}, Budapest, 1981, 1217-1227. 
\bibitem[P4]{P4}
{\sc A. Peth\H o}, {\em  On the solution of the equation $G_n = P(x)$,} in {\em Fibonacci 
Numbers and Their Applications}, D. Reidel Publ. Comp. 1986, 193-201.
\bibitem[P5]{P6} 
{\sc A. Peth\H{o},} {\em The Pell sequence contains only trivial perfect 
powers,} in: Proc. Sets Graphs and Numbers. Coll. Math. Soc. J\'anos Bolyai Vol. 60. pp 561--568. 
\bibitem[P6]{P8} 
{\sc A. Peth\H{o},} {\em Diophantine properties of linear recursive sequences. I.} Bergum, G. E. (ed.) et al., Applications of Fibonacci numbers. Volume 7: Proceedings of the 7th international research conference on Fibonacci numbers and their applications, Graz, Austria, July 15--19, 1996. Dordrecht: Kluwer Academic Publishers. 295-309 (1998). 
 \bibitem[PW]{PW}
{\sc A. Peth\H{o}} and {\sc B.M.M. de Weger,} {\em Product of prime powers in binary recurrence sequences I.,} Math.
Comp. {\bf 47} (1986), 713 -727. 
\bibitem[PSch]{PSch}
{\sc A.J. van der Poorten} and {\sc H.P. Schlickewei,}
{\em The growth conditions for recurrence sequences,} Macquarie Univ. Math.
Rep. 82-0041. North Ryde, Australia.
\bibitem[Schm]{Schm} 
{\sc W.M. Schmidt,} {\em Linearformen mit algebraischen Koeffizienten II.,} Math. Annalen, {\bf 191} (1972), 525--551.
\bibitem[ShT]{ShT} 
{\sc T.N. Shorey} and {\sc R. Tijdeman,} {\em Exponential Diophantine Equations}, 
Cambridge Univ. Press 1986. 
\bibitem[ShSt1]{ShSt1} 
{\sc T.N. Shorey} and {\sc C.L. Stewart,} {\em On the Diophantine
equation $ax^{2t} + bx^ty + cy^2 = d$ and pure powers in recurrences,}
Math. Scand., {\bf 52} (1983), 24--36.
\bibitem[ShSt2]{ShSt2} 
{\sc T.N. Shorey} and {\sc C.L. Stewart,} {\em Pure powers in recurrence sequences
and some related diophantine equations}, J. Number Theory, {\bf 27} (1987) 
324-352.
\bibitem[Sm]{Sm} 
{\sc N.P. Smart}, {\em The Algorithmic Resolution of Diophantine
Equations}, London Math. Soc. Student Text, 41, Cambridge Univ. Press, 1998. 
\bibitem[St]{St} 
{\sc C.L. Stewart,} {\em On some diophantine equations and related linear 
recurrence
sequences}, Seminaire Delange-Pisot-Poitou 1980-81. 
\bibitem[Sz]{Sz} 
{\sc L. Szalay}, {\em On the diophantine equations $(2^n-1)(3^n-1)=x^2$}, Publ. Math. Debrecen {\bf 57} (2000), 1-9.
\bibitem[W]{W} 
{\sc M. Waldschmidt,} {\em Minorations de combinaisons lin\'eares de logarithmes
de nombres alg\'ebriques,} J. Canad. Math. {\bf 45} (1993), 176--224.
\bibitem[Wo]{Wo}
{\sc J. Wolfskill,} {\em Bounding squares in second order recurrence sequences}, Acta
Arith. {\bf 54} (1989) 127-145. 

\end{thebibliography}

\end{document}


