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.
Previous Page Next Page