The by far best known example of a linear recurrence sequence is the
Fibonacci
sequence
given by , and
for
.
In general a linear recurrence sequence is a sequence
of complex numbers given by initial values
and by
a linear recurrence relation

(3)

where
are fixed complex numbers. One may show that
there is only
one recurrence relation satisfied by for which is minimal.
Assuming that in relation (3), is minimal, we call
the *order*, and
the *companion polynomial* of .
Write
,
where
are the distinct roots of and
where
are positive integers.
A basic fact for linear recurrence
relations states that there are polynomials
of degree
such that

for
.
(4)

The sequence is called *simple* if all multiplicities are
,
and *non-degenerate* if none of the quotients
(
) is a root of unity (non-degeneracy implies that for
any
positive integer , the number of zeros of the companion polynomial
of
is equal to the number of zeros
of the
companion polynomial of ).

We are interested in the Diophantine equation , that is,

in
.
(5)

The classical Skolem-Mahler-Lech theorem (cf. [16]) states that
the
number of solutions of (5) is finite if is non-degenerate.
The proof was by means of p-adic analysis. Denote the number of
solutions
of (5) by . An old conjecture attributed to Ward states
that
can be bounded above by a quantity depending on the order of
only.
Throughout the last decades several partial solutions to this problem
have been obtained (Beukers, Tijdeman, Schlickewei, Schmidt). We will
mention
only the most recent result of Schmidt [27],
which completely settles Ward's conjecture.
**Theorem (Schmidt).**
*Suppose is a non-degenerate linear recurrence sequence of
order .
Then
.*

In his proof, Schmidt used the quantitative version of the Subspace Theorem of Schlickewei and the author mentioned above. But apart from that there were some formidable technical difficulties which Schmidt managed to deal with. We mention that for simple linear recurrence sequences, the polynomials in (4) are all constants. So in that case equation (5) is just a special case of equation (2) and then Theorem 1 implies an upper bound for depending only on . The case that not all polynomials are constants turned out to be much harder.