In Chapter 4 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?


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.