In Chapter 4 (page 23, subsection "Somos sequence update") of [his *Tracking the Automatic
Ant*](https://doi.org/10.1007/978-1-4612-2192-0_1), David Gale
discusses three families of recursively defined sequences of numbers, all
due to Dana Scott and inspired by the Somos sequences:



> 
> **Sequence 1.** Fix a positive integer $k\geq 2$. Define a
> sequence $\left( a\_{0},a\_{1},a\_{2},\ldots \right) $ of positive rational
> numbers recursively by setting
> \begin{align\*}
> a\_{n}=1\qquad \text{for each }n<k
> \end{align\*}
> and
> \begin{align\*}
> a\_{n}=\dfrac{a\_{n-1}^{2}+a\_{n-2}^{2}+\cdots +a\_{n-k+1}^{2}}{a\_{n-k}}\qquad 
> \text{for each }n\geq k.
> \end{align\*}
> 
> 
> 



> 
> **Sequence 2.** Fix an **odd** positive integer $k\geq 2$.
> Define a sequence $\left( a\_{0},a\_{1},a\_{2},\ldots \right) $ of positive
> rational numbers recursively by setting
> \begin{align\*}
> a\_{n}=1\qquad \text{for each }n<k
> \end{align\*}
> and
> \begin{align\*}
> a\_{n}=\dfrac{a\_{n-1}a\_{n-2}+a\_{n-3}a\_{n-4}+\cdots +a\_{n-k+2}a\_{n-k+1}}{
> a\_{n-k}}\qquad \text{for each }n\geq k.
> \end{align\*}
> 
> 
> 



> 
> **Sequence 3.** Fix a positive integer $k\geq 2$. Define a
> sequence $\left( a\_{0},a\_{1},a\_{2},\ldots \right) $ of positive rational
> numbers recursively by setting
> \begin{align\*}
> a\_{n}=1\qquad \text{for each }n<k
> \end{align\*}
> and
> \begin{align\*}
> a\_{n}=\dfrac{a\_{n-1}a\_{n-2}+a\_{n-2}a\_{n-3}+\cdots +a\_{n-k+2}a\_{n-k+1}}{
> a\_{n-k}}\qquad \text{for each }n\geq k.
> \end{align\*}
> 
> 
> 


Note the difference between Sequences 2 and 3: The numerator in Sequence 2
is $\sum\limits\_{i=1}^{\left(k-1\right)/2} a\_{n-2i+1} a\_{n-2i}$,
whereas the numerator in Sequence 3 is
$\sum\limits\_{i=1}^{k-2} a\_{n-i} a\_{n-i-1}$.
Thus the requirement for $k$ to be odd in Sequence 2.


Now, Gale claims that all three sequences have the integrality property:
i.e., all their entries $a\_{0},a\_{1},a\_{2},\ldots $ are integers (for all
possible values of $k$). More interesting is the way he claims to prove
this: by constructing an auxiliary sequence that turns out to be constant or
periodic with a small period.


Unfortunately, he only shows this for Sequence 1. Here, the auxiliary
sequence is $\left( b\_{k},b\_{k+1},b\_{k+2},\ldots \right) $, defined by
setting
\begin{align\*}
b\_{n}=\dfrac{a\_{n}+a\_{n-k}}{a\_{n-1}a\_{n-2}\cdots a\_{n-k+1}}\qquad \text{for
each }n\geq k.
\end{align\*}
By applying the recursion of Sequence 1 once to $n$ and once to $n-1$ and
subtracting, it is not hard to see that $b\_{n}=b\_{n-1}$ for each $n\geq k+1$
. Thus, the sequence $\left( b\_{k},b\_{k+1},b\_{k+2},\ldots \right) $ is
constant, and therefore all its entries $b\_{n}$ are integers (since $b\_{k}=k$
is an integer). However, we can solve the equation $b\_{n}=\dfrac{
a\_{n}+a\_{n-k}}{a\_{n-1}a\_{n-2}\cdots a\_{n-k+1}}$ for $a\_{n}$, obtaining $
a\_{n}=b\_{n}a\_{n-1}a\_{n-2}\cdots a\_{n-k+1}-a\_{n-k}$, and this gives a new
recursive equation for the sequence $\left( a\_{0},a\_{1},a\_{2},\ldots \right) 
$. This new recursive equation no longer involves division, and thus a
straightforward strong induction suffices to show that all $a\_{n}$ are
integers (since all $b\_{n}$ as well as the first $k$ entries $
a\_{0},a\_{1},\ldots ,a\_{k-1}$ of Sequence 1 are integers). The details of
this proof can be found in Gale's book or in [the *Notes on mathematical
problem solving* I am currently writing for Math 235 at
Drexel](http://www.cip.ifi.lmu.de/%7Egrinberg/t/20f/mps.pdf)
(Exercise 8.1.8).


Gale claims that similar arguments work for Sequences 2 and 3. And indeed,
this proof can be adapted to Sequence 2 rather easily, by redefining the
auxiliary sequence to be a sequence $\left( b\_{k+1},b\_{k+2},b\_{k+3},\ldots
\right) $ (starting at $b\_{k+1}$ this time) defined by
\begin{align\*}
b\_{n}=\dfrac{a\_{n}+a\_{n-k-1}}{a\_{n-2}a\_{n-3}\cdots a\_{n-k+1}}\qquad \text{
for each }n\geq k+1.
\end{align\*}


I am, however, struggling with adapting this line of reasoning to Sequence
3. If $k$ is odd, then we can set
\begin{align\*}
b\_{n}=\dfrac{a\_{n}+a\_{n-k+1}}{a\_{n-1}a\_{n-3}\cdots a\_{n-k+2}}\qquad \text{
for each }n\geq k-1
\end{align\*}
(where the denominator is $\prod\limits\_{i=1}^{\left( k-1\right) /2}a\_{n-2i+1}$).
The resulting sequence $\left( b\_{k-1},b\_{k},b\_{k+1},\ldots \right) $ is not
constant, but it is periodic with period $2$ (that is, $b\_{n}=b\_{n-2}$ for
each $n\geq k+1$); this is still sufficient for our argument. However, this
only applies to the case when $k$ is odd. (I have found this definition of $
b\_{n}$ in Section 7.5 of [Joshua Alman, Cesar Cuenca, Jiaoyang Huang,
*Laurent phenomenon sequences*, J. Algebr. Comb. (2016)
43:589--633](http://sci-hub.se/10.1007/s10801-015-0647-5), which studies a
more general recursion.)


When $k$ is even, I see no such proof. I assume that the integrality of $
a\_{0},a\_{1},a\_{2},\ldots $ follows from the standard Laurent phenomenon
results known nowadays (by [Fomin, Zelevinsky](https://arxiv.org/abs/math/0104241), [Lam, Pylyavskyy](https://arxiv.org/abs/1206.2611) and others). I haven't properly
checked it, as there are a few technical conditions too many, but it is
certainly consistent with [SageMath
experiments](https://sagecell.sagemath.org/?z=eJxNjjEPgjAQhff-ihenOwNRYuJAdHJxc3KBMJAIpqmWUtqFX29bjHjbvfvu5VM44yjEo-vRkuZSIIzsoXGCWrY4tnPeahQp8OGnDnQuGf1gISE1bKufHRUZFDeJmgP1kpOjWRryGXxdlA2z-Kub_JvMdkwlZDKMHJtmxi7K5IqFiCe99h_2X0VjpXYUlfmnPDikJOJVxav9Am9u98t1wx9yHT7X&lang=sage&interacts=eJyLjgUAARUAuQ==). Alman/Cuenca/Huang do not seem to consider the
$k$-even case in their paper.



> 
> **Question.** Can we prove using the above tools that the
> entries $a\_{0},a\_{1},a\_{2},\ldots $ of Sequence 3 are integers?
> 
> 
> 



Is this Laurent phenomenon explained by invariance/periodicity?
Yes, we can. The argument for odd $k$ made in the Alman/Cuenca/Huang paper was a red herring. We can argue for arbitrary $k \geq 2$ as follows:


Let $n \geq k+2$. Then, the recursive definition of Sequence 3 yields
\begin{align\*}
a\_{n}=\dfrac{a\_{n-1}a\_{n-2}+a\_{n-2}a\_{n-3}+\cdots +a\_{n-k+2}a\_{n-k+1}}{a\_{n-k}}
\end{align\*}
and thus
\begin{align\*}
a\_{n} a\_{n-k} = a\_{n-1}a\_{n-2}+a\_{n-2}a\_{n-3}+\cdots +a\_{n-k+2}a\_{n-k+1} .
\end{align\*}
The same reasoning (applied to $n-2$ instead of $n$) yields
\begin{align\*}
a\_{n-2} a\_{n-k-2} = a\_{n-3}a\_{n-4}+a\_{n-4}a\_{n-5}+\cdots +a\_{n-k}a\_{n-k-1} .
\end{align\*}
Subtracting this equality from the preceding equality, we obtain
\begin{align\*}
a\_{n} a\_{n-k} - a\_{n-2} a\_{n-k-2}
&= \left(a\_{n-1}a\_{n-2}+a\_{n-2}a\_{n-3}+\cdots +a\_{n-k+2}a\_{n-k+1} \right) \\
& \qquad - \left(a\_{n-3}a\_{n-4}+a\_{n-4}a\_{n-5}+\cdots +a\_{n-k}a\_{n-k-1} \right) \\
&= a\_{n-1}a\_{n-2}+a\_{n-2}a\_{n-3} - a\_{n-k+1}a\_{n-k} - a\_{n-k}a\_{n-k-1} .
\end{align\*}
Let us add all the terms $a\_{n-2} a\_{n-k-2}, a\_{n-k+1}a\_{n-k}, a\_{n-k}a\_{n-k-1}$ to both sides of this equality, and throw in an $a\_{n-2} a\_{n-k}$ for good measure. Thus we obtain
\begin{align\*}
&a\_{n} a\_{n-k} + a\_{n-k+1}a\_{n-k} + a\_{n-k}a\_{n-k-1} + a\_{n-2} a\_{n-k} \\
&= a\_{n-1}a\_{n-2}+a\_{n-2}a\_{n-3} + a\_{n-2} a\_{n-k-2} + a\_{n-2} a\_{n-k} .
\end{align\*}
Both sides of this equality can be easily factored, so the equality rewrites as
\begin{align\*}
&a\_{n-k} \left(a\_{n} + a\_{n-2} + a\_{n-k+1} + a\_{n-k-1} \right) \\
&= a\_{n-2} \left(a\_{n-1} + a\_{n-3} + a\_{n-k} + a\_{n-k-2} \right).
\end{align\*}
Dividing this equality by $a\_{n-2} a\_{n-3} \cdots a\_{n-k}$, we obtain
\begin{align\*}
\dfrac{a\_{n} + a\_{n-2} + a\_{n-k+1} + a\_{n-k-1}}{a\_{n-2}a\_{n-3}\cdots a\_{n-k+1}}
&= \dfrac{a\_{n-1} + a\_{n-3} + a\_{n-k} + a\_{n-k-2}}{a\_{n-3}a\_{n-4}\cdots a\_{n-k}} .
\end{align\*}
In other words, $b\_n = b\_{n-1}$, where we define a sequence $\left(b\_{k+1}, b\_{k+2}, b\_{k+3}, \ldots\right)$ of rational numbers by setting $b\_m = \dfrac{a\_m + a\_{m-2} + a\_{m-k+1} + a\_{m-k-1}}{a\_{m-2}a\_{m-3}\cdots a\_{m-k+1}}$ for each $m \geq k+1$. Thus, this sequence $\left(b\_{k+1}, b\_{k+2}, b\_{k+3}, \ldots\right)$ is constant (since we have shown that $b\_n = b\_{n-1}$ for each $n \geq k+2$). Hence, all entries $b\_m$ of this sequence are integers (since it is easily seen that $b\_{k+1}$ is an integer).


Now, we can solve the equality $b\_m = \dfrac{a\_m + a\_{m-2} + a\_{m-k+1} + a\_{m-k-1}}{a\_{m-2}a\_{m-3}\cdots a\_{m-k+1}}$ for $a\_m$, obtaining
\begin{align\*}
a\_m = b\_m a\_{m-2}a\_{m-3}\cdots a\_{m-k+1} - \left(a\_{m-2} + a\_{m-k+1} + a\_{m-k-1}\right)
\end{align\*}
for each $m \geq k+1$. This easily yields (by strong induction on $m$) that all of $a\_0, a\_1, a\_2, \ldots$ are integers (after you check manually that $a\_0, a\_1, \ldots, a\_k$ are integers).


