29
$\begingroup$

The terms of the sequence A276123, defined by $a_0=a_1=a_2=1$ and $$a_n=\dfrac{(a_{n-1}+1)(a_{n-2}+1)}{a_{n-3}}\;,$$ are all integers (it's easy to prove that for all $n\geq2$, $a_n=\frac{9-3(-1)^n}{2}a_{n-1}-a_{n-2}-1$).

But is it also true for the sequence A276175 defined by $a_0=a_1=a_2=a_3=1$ and $$a_n=\dfrac{(a_{n-1}+1)(a_{n-2}+1)(a_{n-3}+1)}{a_{n-4}} \;\;?$$

Update : I crossposted to MO.

$\endgroup$
  • $\begingroup$ If you see what they've written under "comments" in your OEIS link, it is clear that it is not known. It has been checked by computer for the first $40$ terms. $\endgroup$ – Arthur Aug 27 '16 at 7:13
  • $\begingroup$ Yes Arthur, I read it. This sequence has been entered recently in the OEIS... Perhaps a member of this forum will have an idea to solve the problem ? $\endgroup$ – uvdose Aug 27 '16 at 7:32
  • $\begingroup$ That's strange for me. The sequence does not seem to be hardly to calculate. So why has it only been checked till $n=40$? $\endgroup$ – S. M. Roch Aug 27 '16 at 13:53
  • 1
    $\begingroup$ @S.M.Roch my guess is that it grows doubly exponentially ($a_n$ grows like $b^{c^n}$ for some constants $b,c$) $\endgroup$ – mercio Aug 27 '16 at 14:33
  • 5
    $\begingroup$ @S.M.Roch. I made a program : the decimal expansion of $a_{40}$ contains $321865971$ digits. $\endgroup$ – uvdose Aug 27 '16 at 15:19
28
+150
$\begingroup$

Yes, $(a_n)$ is a sequence of integers.

To prove this we first need to study some auxiliary sequences that satisfy a polynomial recurrence relation (unlike $(a_n)$ which has a rational fraction as its recurrence).

Consider the sequences $(b_n)$ of positive reals satisfying the recurrence relation $b_nb_{n+4} = b_{n+1}b_{n+2}b_{n+3} + 1$.

It turns out we can express $b_{n+8}$ as a polynomial in $b_n, \ldots, b_{n+7}$ :

Since $b_{n+1}b_{n+5} \equiv b_{n+2}b_{n+6} \equiv b_{n+3}b_{n+7} \equiv 1 \pmod {b_{n+4}}$ and $b_{n+1}b_{n+2}b_{n+3} \equiv -1 \pmod {b_{n+4}}$, we have $b_{n+5}b_{n+6}b_{n+7} \equiv -1 \pmod {b_{n+4}}$, which suggests the existence of a formula for $b_{n+8}$.

With this roadmap, we can write

$(b_{n+1}b_{n+2}b_{n+3})(b_{n+5}b_{n+6}b_{n+7}+1) \\ = (b_{n+1}b_{n+5})(b_{n+2}b_{n+6})(b_{n+3}b_{n+7}) + (b_{n+1}b_{n+2}b_{n+3}) \\ = (b_{n+2}b_{n+3}b_{n+4}+1)(b_{n+3}b_{n+4}b_{n+5}+1)(b_{n+4}b_{n+5}b_{n+6}+1)+(b_nb_{n+4}-1) \\ = b_{n+4}.F(b_{n+i})$

where $F$ is some big polynomial. And finally,

$(b_{n+5}b_{n+6}b_{n+7}+1) = (b_{n+5}b_{n+6}b_{n+7}+1)(b_nb_{n+4} - b_{n+1}b_{n+2}b_{n+3}) \\ = b_{n+4}(b_nb_{n+5}b_{n+6}b_{n+7}+b_n - F(b_{n+i})) = b_{n+4} G(b_{n+i})$.

And so, $b_{n+8} = G(b_{n+i})$. This means that if $b_0, \ldots, b_7 \in R$ for some subring $R$ of $\Bbb R$, then the whole sequence is in $R$.


Now to link back to the original sequence.

Given such a sequence $(b_n)$, we define a sequence $(a_n)$ by $a_n = b_nb_{n+1}b_{n+2}$.

This sequence satisfies $a_na_{n+4} = (b_n b_{n+1}b_{n+2})(b_{n+4}b_{n+5}b_{n+6}) \\ = (b_n b_{n+4})(b_{n+1} b_{n+5})(b_{n+2} b_{n+6}) = (b_{n+1}b_{n+2}b_{n+3}+1)(b_{n+2}b_{n+3}b_{n+4}+1)(b_{n+3}b_{n+4}b_{n+5}+1) \\ = (a_{n+1}+1)(a_{n+2}+1)(a_{n+3}+1)$.

Finally, taking $b_0 \ldots b_7 = \frac 12, 4, \frac 12, \frac 12, 4, \frac 12, 4, 18$, we obtain a sequence $(b_n)$ with terms in $\Bbb Z[\frac 12]$, with the corresponding $(a_n)$ sequence $1,1,1,1,8,36, \ldots$

Since the recurrence relation is symmetric, it can go backwards as well as forward, hence the ring $R_n = \Bbb Z[b_n, \ldots, b_{n+7}]$ is independant of $n$. There is no hope of finding $8$ consecutive integer values in our sequence $b_n$.

If we look at the sequence $(b_n)$ modulo $8$, from our first octuplet and by applying the polynomial transformation, we can get to $17225$ different octuplets mod $8$, and none of those correspond to any noninteger $a_n$. This computation proves that $a_n$ is an integer forall $n$ (be careful, one step can go from one octuplet to several octuplets, because precision can be lost sometimes).


Note that using this definition,

$a_na_{n+2}/a_{n+1}(a_{n+1}+1) = b_nb_{n+2}b_{n+4}/(b_{n+1}b_{n+2}b_{n+3}+1) = b_{n+2}$,

and so to go in the other direction you have to define $(b_n)$ from $(a_n)$ with $b_n = a_{n-2}a_n/a_{n-1}(a_{n-1}+1)$. Then, once again the recurrence relation of $(b_n)$ follows from that of $(a_n)$.

This shows that for any such rational sequence $(a_n)$, there is a corresponding rational sequence $(b_n)$, and so $(a_n)$ is in a finitely generated subring of $\Bbb Q$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ one might wonder if there is an integer $m$ such that $a_{n+m}$ is a polynomial in the $a_{n+i}$ for $0 \le i < m$. If so, then $m > 55$ because the subsequence $(1,2,1,2)$ is in the middle of a sequence of integers of length $55$ but bordered with nonintegers on both sides. I wouldn't expect such an $m$ to exist. $\endgroup$ – mercio Aug 29 '16 at 14:58
  • 1
    $\begingroup$ I don't understand why the $a_i $ are integers (as opposed to just $2$-integers). Could you be more precise there? Thanks! $\endgroup$ – darij grinberg Feb 22 '19 at 22:17
  • 2
    $\begingroup$ In order to have $a_n$ integer, one would need to demonstrate that the sum of the $2$-adic valuations of three consecutive $b_j$ is non-negative. If it can be shown that $v_2(b_n)$ is periodic (period $11$ apparently), then we are done, because, it would suffice to check the $11$ first sums. $\endgroup$ – René Gy Feb 24 '19 at 21:39
  • 1
    $\begingroup$ @darijgrinberg It seems that this "detail" is hidden in the paragraph about the $17725$ octuples modul 8. I read from this that mercio performed an exhaustive (computer) search during which, among others, $v_2(b_n)$ turned out to remain bounded and $a_n=b_nb_{n+1}b_{n+2}$ an integer. $\endgroup$ – Hagen von Eitzen Feb 28 '19 at 4:33
  • 2
    $\begingroup$ @mercio: What do you mean by "octuplets"? The $b_n$ not being integers, it is strange to look at them mod $8$; are you considering their remainders (maybe upon mutliplication by $32$ or something) or their $2$-adic valuations? And you are saying that $8$ consecutive remainders (or valuations) always uniquely determine the next one? $\endgroup$ – darij grinberg Feb 28 '19 at 15:53

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.