10

1. DEFINITIONS AND TECHNIQUES

then for all r 1,

pr

will divide some term. She has extended this to other bilinear

recurrence sequences (see Section 1.1.20) with k — 4, and has proved several other

conjectures from [1084]. These sequences were originally studied by Michael Somos

in the late 1980's, in an attempt to take a purely combinatorial approach to the

theory of elliptic curves (Zagier has also pondered this possibility.) Jim Propp and

Noam Elkies have been taking strides to try to understand the deep arithmetic and

combinatorial properties of these sequences. The theory is still in its infancy, so we

refer to [421], [422], [775], [1084], [1232] and the web site maintained by Propp

[1052] for more details.

1.1.18. Several variable generalizations. Sequences indexed by N can be

generalized to the multi-variate case. For example, one can consider subsequences

of the coefficients of power series expansions of rational functions in several vari-

ables [736].

Another way to generalize linear recurrence sequences to the many variable

case is as follows. First note that linear recurrence sequences can be considered as

the 'additive' generalization of single exponential functions. One can consider the

'multiplicative' generalization as well. That is, given multiplicatively independent

elements Ai,... , Ar G l consider the finitely-generated multiplicative group

(1.13) V = {\?...\? : xi,... ,xreZ}.

For example, the trace

T

K

/Q(^A^

1

...

A^r)

provides an exponential polynomial in

several variables.

1.1.19. Other linear recurrence relations. For all the sequences men-

tioned thus far, the x-th term a(x) is expressed in terms of one or several previous

terms, typically a(x — 1),... ,a(x — n). A large class of very interesting sequences

is defined by recurrence relations where the x-th term is expressed in terms of more

distant terms, say in terms of

a ([x/2\),... , a ([x/n\) or a (x — [x/2\),... , a (x — [x/n\).

In fact, as has become clear relatively recently, their genesis is in automata the-

ory where these relations arise quite naturally. Generally speaking, such sequences

are beyond our scope. Several interesting examples reveal links to classical linear

recurrence sequences; see Sections 9.3 and 14.1. These sequences arise from nat-

ural questions about binary (or g-ary) expansions of integers; they also arise in

an algorithm for fast computation of elliptic divisibility sequences due to Shipsey

[1166].

Going further, the subscripts may depend on the sequence itself. Some exam-

ples in the number-theory literature are

a(x) = a (x — a(x — 1)) + a (x — a(x — 2))

and

a(x) = a (x — a(x — 1)) + a (a(x — 1))

with a(l) = a(2) = 1 in both cases. The sequence satisfying

a(x) = a(x — a(a(x — 1))) + 1,

sometimes called Golomb's sequence, grows like ( x ^ 5 ) . We refer to [402] and

to [499, Sect. E31] for precise references and some generalizations. A particularly