{<b> Fifth Day ("Sequences")}
<p>
The solutions of these problems are somewhat longer and I only give highlights.
<p>
1.  The sequence \{t<sub>n\}<sub>n starts 1, 1, 1, 1, 1, 2, 3, 5, 11, 37, 83, \dots  It is required to show that
all of the t<sub>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<sub>n,y<sub>n) where the exact denominators of x<sub>n and y<sub>n are t<sub>n<sup>2 and t<sub>n<sup>3, respectively, for
some integer t<sub>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<sub>nt<sub>{n + 5} = t<sub>{n + 1}t<sub>{n + 4} + t<sub>{n + 2}t<sub>{n + 3} by t<sub>{n + 1}t<sub>{n + 4} gives the simpler
recursion w<sub>nw<sub>{n + 2} = 1 + 1/w<sub>{n + 1} for the numbers w<sub>n: = t<sub>{n + 3}t<sub>n/t<sub>{n + 1}t<sub>{n + 2}.  This says that the seqence of
pairs (X,Y) = (w<sub>n,w<sub>{n + 1}) is generated from the initial value (X,Y) = (1,1) by 
(X,Y)\mapsto(Y,(1 + Y<sup>{ - 1})/X).  A picture shows that these points (w<sub>n,w<sub>{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) = \bigl(2\frac{X + Y - 2}{Y + X - 5},\,2\frac{Y - 2X + 1}{X + Y - 5}\bigr).

The other method is more analytic: one computes the
first few (in my case, 300) terms t<sub>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<sup>2, but with
some slow fluctuations around this and also with a dependency on the parity of n. This suggests trying the Ansatz
 t<sub>n  =  C<sub>\pm B<sup>nA<sup>{n<sup>2}, where ( - 1)<sup>n = \pm1.
This is easily seen to give a solution to our recursion if A is the root of A<sup>{12} = A<sup>4 + 1, and the numerical value
A\approx 1.07283 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<sub>\pm replaced by a function C<sub>\pm(n) which lies between
fixed limits but is almost periodic in n, and this works, but with a new value A\approx1.07425. (The coefficient 
C<sub>\pm(n) in fact depends on the position of the point (w<sub>n,w<sub>{n + 1}) on the above - mentioned curve (XY - 1)(5 - X - Y) = 6.) 
Expanding the function C<sub>\pm(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<sub>n one can replace the above (E,P) by essentially 
any elliptic curve over \Bbb 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!

<p>
2. The sequence \{u<sub>n\}<sub>n starts \frac54, \frac{51}{14}, \frac{277}{20}, \frac{1497}{26}.
\frac{4045}{16}, \dots It is required to show that the first integral u<sub>n is u<sub>{2755452}\approx 10<sup>{2019025}\,.
The first step is to note that the numbers U<sub>n = (6n + 2)u<sub>n satisfy the recursion relation
U<sub>{n + 3} = U<sub>n + 2U<sub>{n + 1} + 5U<sub>{n + 2} (the proof is elementary and I omit it) and hence are all integral.
One must thus show that the congruence U<sub>n\equiv0\pmod{6n + 2} holds for n<sub>0 = 2755452 and
for no smaller value of n.  (To find the approximate size of u<sub>{n<sub>0} is then easy since the
explicit solution of the recursion gives U<sub>n\sim AB<sup>n with A = 1.75487766624669276 ...  , B = 5.40431358073618481197 ...  .)
Again the detailed proof is complicated and I skip it, mentioning only that this is in the same category as the problem of finding
pseudoprimes (for instance, a 2 - pseudoprime is a composite integer n for which the nubmer 2<sup>{n - 1}\equiv1\pmod n, and this is
a similar condition to the integrality of u<sub>n since the numbers 2<sup>{n - 1} - 1 satisfy a linear recursion T<sub>{n + 2} = 3T<sub>{n + 1} - 2T<sub>n
similar to that of the U<sub>n) and can be analyzed by studying the splitting behavior of the cubic polynomial X<sup>3 - 5X<sup>2 - 2X - 1
modulo varying primes.
<p>
3. The sequence \{v<sub>n\}<sub>n starts 2, 3, 5, 10, 28, 154, 3520, 1551880, 267593772160, 7160642690122633501504, \dots
It is required to show that the first non - integral v<sub>n is v<sub>{43}\approx 5.4093\times10<sup>{178485291567}\,. Again, the only problem is
to show that the first index n<sub>0 with v<sub>{n<sub>0}\notin\Z is n<sub>0 = 43, since the size of v<sub>{n<sub>0} then follows from the
easily proved formula v<sub>n\sim(n<sup>2 + 2n - 1 + 4n<sup>{ - 1} - 21n<sup>{ - 2} + 137n<sup>{ - 3} - \dots)\times C<sup>{2<sup>n} with 
C = 1.04783144757641122955990946274313755459\dots.  We first replace v<sub>n by  s<sub>n = 2 + v<sub>1<sup>2 +  ...   + v<sub>{n - 1}<sup>2 = nv<sub>n. Then
 the recursion becomes s<sub>{n + 1} = s<sub>n = s<sub>n<sup>2/n<sup>2 with initial condition s<sub>1 = 2. Let us look at one prime p at a time. The
first s<sub>n which could fail to be p - integral is s<sub>{p + 1}, which will happen if and only if s<sub>p is not divisible
by p, so we can test this by looking at the sequence \{s<sub>1,s<sub>2, ...  ,s<sub>p\} modulo p.  This is an easy 
calculation since the numbers s<sub>j (mod p) do not grow, and we find with a couple of minutes on a computer
that s<sub>p\equiv0\pmod p for each prime p<43 but not for 43. (Note that this calculation cannot be done directly
since no computer can compute or store the s<sub>n's for n bigger than about 22.)  This proves that v<sub>{43} is
not integral (it has a denominator divisible by 43), and that v<sub>p is at least p - integral for p less than 43;
to check that v<sub>n is actually integral for n &lt;= 42 we must only compute the sequence s<sub>n modulo quite modest
powers of primes less than 43, and this is easily done on the computer.   The real question is why the congruence
s<sub>p\equiv0\pmod p holds for all primes less than 43, since naively one would think that its probability of
holding for even one prime p is about 1/p, which is quite small.  But in fact its probability of holding for
a given p is quite large, since in the recursion for the s<sub>n, if any s<sub>n with n<p happens to take on
the value  - n<sup>2 mod p then all of the following s<sub>n are 0 mod p, and the chance of this happening can be
expected to be about 63\%; also, this argument holds for any initial value s<sub>1, and the value s<sub>1 = 2 has been
chosen to make the first few primes behave. 

\end