Next: The Subspace Theorem Up: Diophantine Equations and Diophantine Previous: Linear equations with unknowns

# Linear recurrence sequences

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.

Next: The Subspace Theorem Up: Diophantine Equations and Diophantine Previous: Linear equations with unknowns