<s>[INST] Is this Laurent phenomenon explained by invariance/periodicity? In Chapter 4 (page 23, subsection "Somos sequence update") of his Tracking the Automatic
Ant, 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
(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, 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, Lam, Pylyavskyy 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. 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?

 [/INST] 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).
</s>