The sequence defined by $a_0=a_1 =1$ and $$ a_n = \frac{1}{n-1}\sum_{i=0}^{n-1}a_i^2, \quad n > 1 $$ fails to be integer for the first time at $a_{44}$. Why??

You can verify the statement by computing the sequence mod 43 (see more commentary here (day 5, problem 3)). That's not a very satisfying answer though. Is there a good reason for this behavior?


Copying my explanation from https://mathoverflow.net/a/217894/25028

The recurrence formula can be rewritten as $$a_2=2,\qquad a_{n+1}=\frac{a_n\cdot (a_n+n-1)}n,\quad n\geq 2,$$ which somewhat justifies why $a_n$ remains integer for quite a while. It shows that $a_n$ accumulates most of the factors of the previous terms and gains some new ones. The division by $n$ happens to hit the existing factors up until $n=43$.

Another example of this kind is given by $$b_2=2,\qquad b_{n+1}=\frac{b_n\cdot (b_n+n+5)}n,\quad n\geq 2,$$ which remains integer for up to $n=59$.

ADDED. OEIS A292996 gives indices of first noninteger terms in similar sequences.

Some spin-off questions:

  • 7
    $\begingroup$ Is there any positive sequence of this type ($c_{n+1}=c_n(c_n+n+\alpha)/n$ with integer $\alpha$ which remains integer forever? $\endgroup$ – Ilya Bogdanov Sep 27 '17 at 15:17
  • 1
    $\begingroup$ @IlyaBogdanov: Good question! I don't have an immediate answer. It may be worth to ask it at MO separately. $\endgroup$ – Max Alekseyev Sep 27 '17 at 15:22
  • $\begingroup$ OK, let me do it. $\endgroup$ – Ilya Bogdanov Sep 27 '17 at 15:25
  • $\begingroup$ @MaxAlekseyev: the recursion only holds for $n\geq2$, right? $\endgroup$ – Sam Hopkins Sep 27 '17 at 16:21
  • 1
    $\begingroup$ @AntoinedePaladin: There are many such examples with growing records. E.g., $c_2=2$ and $c_{n+1}=c_n(c_n+n+16)/n$ give integers when $n<73$. $\endgroup$ – Max Alekseyev Sep 27 '17 at 21:41

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.