- MacTutor History of Mathematics

Solution: Day 5, problem 1

The solutions of the fifth day problems problems are somewhat longer and we only give highlights.

The sequence

( t_{n} )

starts 1, 1, 1, 1, 1, 2, 3, 5, 11, 37, 83, ... It is required to show that all of the

t_{n}

are integral. The proof comes from the theory of elliptic curves, and can be expressed either in terms of the denominators of the coordinates of the multiples of a particular point on a particular elliptic curves, or in terms of special values of certain Jacobi theta functions. In the first version, one computes the point

nP + T

on the elliptic curve

E : y(x + y) = x(x - 1)(x + 2)

, where

T

is the 2 - torsion point (0,0) and

P

is the point of infinite order (2,2); this has the form

(x_{n}, y_{n})

where the exact denominators of

x_{n}

and

y_{n}

are

t_{n}^{2}

and

t_{n}^{3}

, respectively, for some integer

t_{n}

, and the rules of computation on elliptic curves lead to the given recursion for the

t

's. I'll omit the analysis, indicating instead two ways that one could be led to find this solution.

The first is algebraic.
Dividing the recursion

t_{n}t_{n+5} = t_{n+1}t_{n+4} + t_{n+2}t_{n+3}

t_{n+1}t_{n+4}

gives the simpler recursion

w_{n}w_{n+2} = 1 + 1/w_{n+1}

for the numbers

w_{n} = t_{n+3}t_{n}/t_{n+1}t_{n+2}

. This says that the seqence of pairs

(X, Y) = (w_{n},w_{n+1})

is generated from the initial value

(X, Y) = (1, 1)

(X, Y) \mapsto (Y, (1 + Y^{-1})/X)

. A picture shows that these points

(w_{n}, w_{n+1})

all lie on a curve, which is then easily found to be given by the equation

(XY - 1)(5 - X - Y) = 6

. This is a curve of genus 1 which is isomorphic to the above

E

via

(x,y) = ( 2(X + Y - 2)/(Y + X - 5), 2(Y - 2X + 1)/(X + Y - 5) )

.

The other method is more analytic: one computes the first few (in my case, 300) terms

t_{n}

numerically, studies their numerical growth, and tries to fit this data by a nice analytic expression. One quickly finds that the growth is roughly exponential in

n^{2}

, but with some slow fluctuations around this and also with a dependency on the parity of

n

. This suggests trying the Ansatz

t_{n} = C_{±} B^{n}A^{n^2}

, where

(- 1)^{n} = ± 1

. This is easily seen to give a solution to our recursion if

A

is the root of

A^{12} = A^{4} + 1

, and the numerical value

A = 1.07283

(approx) does indeed give a reasonably good fit to the data, but eventually fails more and more thoroughly. Looking more carefully, we try the same Ansatz but with C± replaced by a function

C_{±}(n)

which lies between fixed limits but is almost periodic in

n

, and this works, but with a new value

A = 1.07425

(approx). (The coefficient

C_{±}(n)

in fact depends on the position of the point

(w_{n}, w_{n+1})

on the above-mentioned curve

(XY - 1)(5 - X - Y) = 6.

) Expanding the function C± (n) numerically into a Fourier series, we discover that it is a Jacobi theta function, and since theta functions (or quotients of them) are elliptic functions, this leads quickly to elliptic curves and to the above curve

E

.

By the way, by varying the coefficients in the recursion for the

t_{n}

one can replace the above

(E, P)

by essentially any elliptic curve over Q and any rational point on it, so that in an elementary course in number theory one could develop (or at least introduce) the entire theory of elliptic curves just by starting with these simple recursions!