# Simple Somos Sequence

Browsing through an old collection of Russian olympiad problems, I noticed one that I marked *solved* years ago, when a highschooler. For the life of me I could not remember the solution I came up with at the time. The problem has been offered at the final stage of the XXVI (1963) Moscow Mathematical Olympiad, senior class.

The sequence a_{1}, a_{2}, a_{2}, ... is defined iteratively

a_{1} = 1, a_{2} = 1,

a_{n} = (a_{n-1}^{2} + 2) / a_{n-2}, n ≥ 3.

Prove that all members of the sequence are positive integers.

The sequence, so simply defined, falls into the category of Elliptic Sequences discovered by M. Somos in the mid-1970s. As I do not remember my old solution, I shall simply adopt the approach that worked for more complex Somos sequences.

Let's find a few first members of the sequences: 1, 1, 3, 11, 41, 153, ... An immediate observation is that all of the numbers are odd. More generally, if the process indeed generates an integer sequence then all the members of the sequence are bound to be odd. The proof is by induction: if a_{n-1} is odd, then so is its square increased by 2. When divided by an integer a_{n-2} it may only give another odd number.

But more is true: in any triple of successive terms, the members of the sequences are pairwise prime:

gcd(3, 11) = gcd(3, 41) = gcd(11, 41) = 1 and also

gcd(11, 41) = gcd(11, 153) = gcd(41, 153) = 1,

but, of course, gcd(3, 153) = 3 ≠ 1. The claim is actually obvious as any common factor of a_{n} and a_{n-1} (which are both odd) would divide 2, i.e., 1.

Denote some four consecutive terms of the sequence a, b, c = (b² + 2) / a, d = (c² + 2) / b and suppose that these and all the preceding terms are integers. We want to show that the next term

Observe that d ≡ 2/b (mod c), which is a regular residue modulo c because c and b are mutually prime. Let's write _{0} + C,_{0} is the residue modulo c equal to 2/b, and C is a multiple of c.

We have

c·e | = (d_{0} + C)² + 2 | |

= (d_{0})² + (2Cd_{0} + C²) + 2 | ||

≡ (2/b)² + 2 (mod c) | ||

≡ (b² + 2) / a · 2a / b² (mod c) | ||

≡ c · 2a / b² (mod c) | ||

≡ 0 (mod c), |

because again b and c are mutually prime. It follows that ce is divisible by c so that, indeed, e is an integer.

Simple as it is, the fact that the algorithm generates an integer sequence is really unexpected (from the pre-Somos view point). As if it were not enough, the algorithm admits a generalization: 2 in the numerator can be replaced with any positive integer m: _{n} = (a_{n-1}^{2} + m) / a_{n-2}

This is also true for some combinations of the initial conditions and m. If a_{0} = a, and a_{1} = b, then, for example, the triples

A calculator that lists a few dozens terms of the sequence is available on a separate page.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny