8

1. DEFINITIONS AND TECHNIQUES

1.1.16. Non-linear recurrence relations; in particular continued frac-

tions. A non-linear recurrence sequence satisfies a relation of the form

(1.9) a(x + n) — F (x,a(x + n — 1),... ,a(x)), x E Z

+

.

Here F is often a polynomial or a rational function, or some arithmetic function.

Even choosing the simplest functions F yields a great variety of interesting se-

quences, from coefficients of algebraic functions and of solutions to differential

equations, to the sequences appearing in the still unsolved

c3x

+ 1' or 'Collatz'

problem (see Chapter 3). Even when n = 1 and F is independent of x, this encom-

passes iterations of functions as dynamical systems — see [581] for an attractive

overview.

Non-linear recurrences can be used to define novel entire functions. A striking

recent example is the recurrence

x-l

a(x + 1) = x2a(x) + ] T a(j)a(x + 1 - j), k 2, a(2) = a(l) - a(l) 2 ,

which arises in the tritronquee solution of a Painleve equation [564]. In [541] it is

shown that the limit lima:_+00 a(x)/[(x — l)!]2 exists and defines an entire function

of a(2).

A particularly important example of a non-linear recurrence sequence for num-

ber theory is given by the Gauss map

F(x)

=

{i}'

x^0'

where {z} denotes the fractional part of z G R. Define the notation [c$ , C\, c2 , .. • ],

by

[CO , Ci , C2 , . . . , Cn] = Co + l / [ c i , C2 , . . . , C

n

].

If a = [CQ , c\ , C2 , . •. ] is the continued fraction expansion of an irrational real

number then the sequence a$ = [a\, ax+i = F(ax), x = 0,1, 2,... , is the sequence

of complete quotients ax — [cx , cx+\ , ... ].

The continued fraction expansion of a quadratic irrational is eventually peri-

odic, which implies that the numerators px and denominators qx of its convergents

satisfy linear recurrence relations. In Section 9.2 we shall see that the converse

holds as well.

It is pointed out in [129] that for any algebraic number a the convergents

Px/Qx satisfy a non-linear recurrence relation. Specifically, the partial quotients cx

are given in terms of the previous convergents and the defining polynomial of the

algebraic number. For example, in the case a = one has

1 3 ( - l ) ^ 2 _

1

qx_2 I

L ^ - i ( P x - i - 2 ^ - i ) Qx-i\'

The continued fraction map is ergodic with respect to an absolutely continuous

measure on (0,1), which gives many results on the behaviour of typical orbits under

F, and hence of the continued fraction expansion for almost every real number

(see [260] or [280] for these results, and [1152] for an extensive discussion of

generalizations of the continued fraction map; a 'normal number' for the continued

fraction map, analogous to Champernowne's classical result in [219], is exhibited

in [2]). Further work on normality, ergodicity and Diophantine properties for the