## 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} by *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) by (*X*, *Y*) ↦ (*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* - 2*X* + 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*^{n2}, 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!