### A Somos Sequence

Somos sequences are sequences that are defined by certain nonlinear recurrence relations. The Somos-k sequence obeys the recurrence relation

$a_n a_{n-k} = \sum\limits_{i=1}^{\lfloor k/2 \rfloor} a_{n-i} a_{n-k+1}$

with initial values $a_n = 1$ for $0 \le n \le k-1\ .$

The first interesting case is $k = 4$:

$a_n a_{n-4} = a_{n-1} a_{n-3} + (a_{n-2})^2$

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 $a_n$ is always a positive rational number. It is not at all obvious that $a_n$ 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 $a_{n-4}, a_{n-3}, a_{n-2}, a_{n-1}$ are pairwise coprime for some n, and let p be a a prime divisor of (the numerator of) $a_n$. Then p divides $a_n a_{n-4}$, so p also divides $a_{n-1} a_{n-3} + (a_{n-2})^2$. From this we conclude that

$p\ |\ a_{n-2} \iff (p\ |\ a_{n-1})\$ or $\ (p\ |\ a_{n-3})\ .$

But p cannot divide two of the terms $(a_{n-3}, a_{n-2}, a_{n-1})$, because we assumed that they are coprime. Therefore, p divides none of them; so $(a_{n-3}, a_{n-2}, a_{n-1}, a_n)$ are coprime. This completes the induction step.

Direct calculation shows that (at least) the first eight terms are integers. Consider nine consecutive terms

$a, b, c, d, e, f, g, h, i$

and suppose that the first eight terms are integers. We will show that i is also an integer.

The recurrence yields the following equations.

$ae = bd + c^2$

$bf = ce + d^2$

$cg = df + e^2$

$dh = eg + f^2$

$ei = fh + g^2$

Reducing the equations modulo e yields the following equations. (The divisions are allowed because b, c, d, and e are coprime.)

$bd + c^2 \equiv 0$

$f \equiv \dfrac{d^2}{b}$

$g \equiv \dfrac{df}{c} \equiv \dfrac{d^3}{bc}$

$h \equiv \dfrac{f^2}{d} \equiv \dfrac{d^4}{b^2d} \equiv \dfrac{d^3}{b^2}$

$ei \equiv \dfrac{d^5}{b^3} + \dfrac{d^6}{b^2c^2}$

Step 3: A lucky factorization.

Observe that we can write the final equation as

$ei \equiv \dfrac{d^5}{b^3 c^2} (c^2 + bd)$.

But $c^2 + bd \equiv 0$, so $ei \equiv 0 \pmod{e}$.

This implies that i is an integer.