Fix an integer $k\geq3$. Define the two families of sequences $\{x_n\}$ and $\{y_n\}$ according to the rules: $$x_n=\frac{x_{n-1}^2+x_{n-2}^2+\cdots+x_{n-k+1}^2}{x_{n-k}} \qquad n\geq k$$ and $$y_n=\frac{(y_{n-1}+y_{n-2}+\cdots+y_{n-k+1})^2}{y_{n-k}} \qquad n\geq k$$ with initial conditions $x_j=y_j=1$ for $j=0,1,\dots,k-1$.


(1) It seems that both $x_n$ and $y_n$ are always positive integers.

(2) It also appears true that $y_n=x_n^2$ for all $n$.

Any ideas of a proof? Of course, if (2) holds and $x_n\in\mathbb{N}$ then $y_n\in\mathbb{N}$.

REMARK. Special cases are also appreciated, say for $k=3$ etc.

  • 4
    $\begingroup$ $x_n$, for $k=3$, is tabulated at oeis.org/A064098 with much information and many links. Undoubtedly, some other parameter values are also represented at OEIS. $\endgroup$ Nov 16 '16 at 4:37
  • $\begingroup$ @GerryMyerson: I understand, not so surprised. My main interest is question #2. $\endgroup$ Nov 16 '16 at 4:40
  • 1
    $\begingroup$ Question 2 is also mentioned (for the case $k=3$) at the page in my link, the third comment, Benoit Cloitre, 28 July 2002. $\endgroup$ Nov 16 '16 at 4:49
  • $\begingroup$ Thanks, again. I see no proof though. In any case, let us ask for $k>3$. $\endgroup$ Nov 16 '16 at 5:01
  • 2
    $\begingroup$ The sequence $\{x_n\}$ (with arbitrary $k$) was mentioned in the "Strange and Surprising Saga of the Somos Sequences" by D. Gale (see his book "Tracking the automatic ant and other mathematical explorations"). Accordind to this article it was discovered by Dana Scott. $\endgroup$ Nov 16 '16 at 5:04

Suppose we know that $y_j=x_j^2$ for $j=n-1, \ldots, n-k$. Then $$x_n^2=\left(\frac{x_{n-1}^2+x_{n-2}^2+\cdots+x_{n-k+1}^2}{x_{n-k}} \right)^2=\frac{(y_{n-1}+y_{n-2}+\cdots+y_{n-k+1})^2}{y_{n-k}} =y_n.$$

If all $y_n$ are integers then from requrrent relation follows that they are squares. It means that all $x_n$ are also integers. So $\{y_n\}$ are integers iff $\{x_n\}$ are integers.

Integrality of $\{x_n\}$ is a special case of more general result (see case (1) in Theorem 3.9 from the article Laurent Phenomenon Sequences by Joshua Alman, Cesar Cuenca and Jiaoyang Huang).

  • $\begingroup$ to be precise, to start the induction, one should add the observation that $x_j^2=y_j$ for $j<k$ :) $\endgroup$ Nov 16 '16 at 5:43
  • 1
    $\begingroup$ Yes, it's important to check for $j<k$. This suggests that (2) is still valid if the initial conditions satisfy $y_j=x_j^2$ instead of just $y_j=x_j=1$. $\endgroup$ Nov 16 '16 at 13:35

As to Question 2, the sequence $(x_n^2)$ solves the same recursive relation as $(y_n)$, with the same initial values, therefore they coincide.

  • $\begingroup$ Can you show how? $\endgroup$ Nov 16 '16 at 5:31
  • $\begingroup$ As usually done: square both sides of the relation for the $x_n$, then call $x_n^2=Y_n$, getting a recursion for $Y_n$, which is the one you already have for $y_n$, with the same initial conditions, so $y_n=Y_n$ for all $n$. $\endgroup$ Nov 16 '16 at 5:43

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.