16
$\begingroup$

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?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
24
$\begingroup$

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:

Improve this answer
$\endgroup$
9
  • 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, 2017 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, 2017 at 15:22
  • $\begingroup$ OK, let me do it. $\endgroup$
    – Ilya Bogdanov
    Sep 27, 2017 at 15:25
  • $\begingroup$ @MaxAlekseyev: the recursion only holds for $n\geq2$, right? $\endgroup$
    – Sam Hopkins
    Sep 27, 2017 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, 2017 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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