A Somos Sequence
by David Radcliffe
Somos sequences are sequences that are defined by certain nonlinear recurrence relations. The Somos-k sequence obeys the recurrence relation
with initial values for
The first interesting case is :
The first 15 terms of the Somos-4 sequence (A006720) are
1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898.
It is easy to prove by induction that is always a positive rational number. It is not at all obvious that is always an integer, but this is true as well. I will present a proof due to Janice Malouf and George Bergman.
Step 1: Four consecutive terms are coprime.
We first show that any four consecutive terms are pairwise coprime. The proof is by induction. It is obvious that the first four terms are pairwise coprime. Assume that are pairwise coprime for some n, and let p be a a prime divisor of (the numerator of) . Then p divides , so p also divides . From this we conclude that
But p cannot divide two of the terms , because we assumed that they are coprime. Therefore, p divides none of them; so are coprime. This completes the induction step.
Step 2: Modular madness!
Direct calculation shows that (at least) the first eight terms are integers. Consider nine consecutive terms
and suppose that the first eight terms are integers. We will show that i is also an integer.
The recurrence yields the following equations.
Reducing the equations modulo e yields the following equations. (The divisions are allowed because b, c, d, and e are coprime.)
Step 3: A lucky factorization.
Observe that we can write the final equation as
But , so .
This implies that i is an integer.