1.1. MAIN DEFINITIONS AND PRINCIPAL PROPERTIES

11

interesting doubly-indexed sequence from computer science is Ackerman's function

A : N2 - • N, defined by

,4(0, n) = n + 1

A ( r a + 1 , 0 ) = A(ra,l )

A(ra + l,rc + l) = A(m,A( m + l,n)) ;

see [197] for a historical perspective on this function.

1.1.20. Bilinear recurrence sequences. The set of linear recurrence se-

quences forms a ring because this structure is inherent in the set of exponential

polynomials. A sequence u is a bilinear recurrence sequence if it satisfies, for some

fc, the finite relation

u(x)u(x — k) = Y ^ CLJU(X — j)u{x — k + i)

i-\-j = k;lij

where 2i, a^ . . . , a^/2j a r e constants.

If k = 4 or 5, the sequence is said to be binary (because in both cases there is

the same number of terms). Similarly, when k = 6 or 7, the sequence is said to be

ternary and so on. Notice that every linear recurrence sequence of order k is also a

bilinear recurrence sequence of order k.

Remarkably, the set of bilinear recurrence sequences seems to exhibit closure

properties under multiplication much as the set of linear recurrence sequences does.

For example, the sequence S defined on page 164 and starting

0,1,1, - 1 , 1 , 2, - 1 , - 3 , - 5 , 7, - 4 , - 2 3 , 29, 59,129, -314 , -65,1529, -3689, -8209,

squares to a ternary bilinear recurrence sequence with relation

u{x)u{x - 6) = -u(x - l)u(x - 5) + 2u{x - 2)u{x - 4) + 2u{x - 3) 2 .

More generally, the product of two elliptic divisibility sequences (see Chap-

ter 10) is (generically) a quaternary bilinear recurrence sequence. To see how these

kind of relations appear, notice that an elliptic recurrence relation can be written,

for each fc, in the form

u(x + k)u(x — k) — Aku(x + l)u(x — 1) + Bku(x)2.

Squaring the equations for k = 2 and k = 3 enables the term in u(x+l)u(x — l)u(x)2

to be eliminated, leaving a relation

u(x + 3)2u(x - 3) 2 = axu[x + 2)2u(x - 2)2 + a2u(x + l)2u{x - l ) 2 + a3u(x)4.

Now replace x by x — 3. This kind of proof, starting instead with three equations,

can be used to show that a generic product of two elliptic divisibility sequences

satisfies a quaternary bilinear recurrence relation. Note that, just as in the linear

case, the relation can degenerate to one of lower order.

This closure property suggests many bilinear analogues of the results we will

present for the linear case.

The thesis [1268] also contains a proof of the following result due to Nelson

Stephens. Every bilinear recurrence with k = 4 arises (up to a natural notion of

equivalence) either from an elliptic divisibility sequence or as

U[n) = ( — 1)

Xn^iXn_2Xn-3

• ' '

Xl X0

where (xn,yn) = Q + nP for points Q and P = [0,0] on a suitable elliptic curve.