求证一个三阶递推数列的各项都是整数

hbghlyj

设数列$\{a_n\}$满足$a_0=a_1=a_2=a_3=a_4=1,a_{n+4}a_n=a_{n+3}a_{n+1}+a_{n+2}^2$，求证：$a_n$都是整数

Tesla35

套路?

tommywong

哩個叫做Somos-4 sequence

sciencedirect.com/science/article/pii/0012365X9290714Q?via%3Dihub

入面用數歸證嘅,假設連續八項成立
先證連續兩項互質$gcd(B(4),B(3))=1$,再證與其後三項互質$gcd(B(4),B(2)B(1))=1$(或$gcd(B(4),B(3)B(2)B(1))=1$),
最後證$B(1)B(2)B(8)\equiv B(1)B(2)[B(5)B(7)+B(6)^2]\equiv 0\pmod{B(4)}$

kuing

回复 3# tommywong

这么难……
不像 2# 说的套路……

PS、可以用 \gcd 输入最大公约数 $\gcd$

tommywong

回复  tommywong

这么难……
不像 2# 说的套路……

PS、可以用 \gcd 输入最大公约数 $\gcd$ ...
kuing 发表于 2019-11-21 17:13

套路就是去OEIS找

kuing

回复 5# tommywong

hbghlyj

tommywong 发表于 2019-11-21 09:56
哩個叫做Somos-4 sequence

sciencedirect.com/science/article/pii/0012365X9290714Q?via%3Di ...

The following problem was communicated to us by Ronald L. Graham. The sequence of numbers $\left\{a_{i}\right\}$ defined recursively in the abstract begins 1,1,1,1,2,3,7,23,59,314,1529,8209,83313,620297,7869898,126742987,1687054711,$\ldots$, and grows on the order of $\exp \left(n^{2}\right)$[1].

It had been observed that more than a hundred values of the sequence were integers and a proof that the entire sequence is integral was sought. We show in Theorem 1 that the sequence is indeed integral and discuss some generalizations.
Theorem 1. The sequence $\left\{a_{i}\right\}$ defined by the recurrence
$$\tag1
a_{n}=\frac{a_{n-3} a_{n-1}+a_{n-2}^{2}}{a_{n-4}} \text { for } n>3
$$
with initial values $a_{0}=a_{1}=a_{2}=a_{3}=1$ is integral.
Proof. To show the sequence consists only of integers, we assume that the sequence is integral up to and including eight consecutive members $B(0), B(1), B(2), \ldots, B(7)$. To show that $B(8)$ and hence the rest of the sequence is integral, we need to show that
$$
B(5) B(7)+B(6)^{2} \equiv 0\pmod{B(4)}
$$
We first show in Lemma 1 that $B(4)$ is relatively prime to $B(1) B(2)$, and then complete the proof by showing in Lemma 2 that $B(1) B(2)\left[B(5) B(7)+B(6)^{2}\right] \equiv 0\pmod{B(4)}$.

Lemma 1. The numbers $B(4)$ and $B(1) B(2)$ are relatively prime.
Proof. We first observe that as long as the sequence is integral, consecutive members are relatively prime. For if a prime $p \mid a_{n}$ and $p \mid a_{n-1}$, then from the recurrence (1), we also have $p \mid a_{n-2}$. Then from $p \mid \operatorname{gcd}\left(a_{n-1}, a_{n-2}\right)$, we have $p\left|a_{n-3}, \ldots, p\right| a_{2}=1$. Now let $p$ be a prime divisor of $B(4)$. Then $p$ cannot divide $B(1)$, else $B(1) B(5)=B(2) B(4)+B(3)^{2}$ implies $p \mid B(3)$. Also, since $B(0) B(4)=B(1) B(3)+B(2)^{2}, p$ cannot divide $B(2)$, for otherwise we have $p \mid B(1) B(3)$.

Lemma 2. The sum $B(5) B(7)+B(6)^{2} \equiv 0\pmod{B(4)}$
Proof. We use the recursion formula (1) for $B(n)$, with $n=4,5,6,7$ to get the identities
\begin{align}B(0) B(4)=B(1) B(3)+B(2)^{2} \tag i\\ B(1) B(5)=B(2) B(4)+B(3)^{2}\tag{ii} \\ B(2) B(6)=B(3) B(5)+B(4)^{2} \tag{iii}\\ B(3) B(7)=B(4) B(6)+B(5)^{2}\tag{iv
}\end{align}So that, applying (ii), (iv), (iii), again (iii), and (i),
$$
\begin{aligned}
B(5) B(7)+B(6)^{2} & \equiv B(1) B(2) B(5) B(7)+B(1) B(2) B(6) B(6) & & \text { from Lemma } 1 \\
& \equiv B(2) B(3) B(3) B(7)+B(1) B(2) B(6) B(6) & & \text { by (ii) } \\
& \equiv B(2) B(3) B(5) B(5)+B(1) B(2) B(6) B(6) & & \text { by (iv) } \\
& \equiv B(2) B(3) B(5) B(5)+B(1) B(3) B(5) B(6) & & \text { by (iii) } \\
& \equiv B(2) B(2) B(5) B(6)+B(1) B(3) B(5) B(6) & & \text { by (iii) } \\
&=B(5) B(6)[B(1) B(3)+B(2) B(2)] & \\
& \equiv 0\pmod{B(4)} \quad \text { by (i). }
\end{aligned}
$$

hbghlyj

en.wikipedia.org/wiki/Somos_sequence

For an integer number $k$ larger than 1, the Somos-$k$ sequence $(a_0, a_1, a_2, \ldots )$ is defined by the equation $$a_n a_{n-k} = a_{n-1} a_{n-k+1} + a_{n-2} a_{n-k+2} + \cdots + a_{n-(k-1)/2} a_{n-(k+1)/2}$$ when $k$ is odd, or by the analogous equation $$a_n a_{n-k} = a_{n-1} a_{n-k+1} + a_{n-2} a_{n-k+2} + \cdots + (a_{n-k/2})^2$$ when $k$ is even, together with the initial values : $a$_$i$ = 1 for $i<k$.

For $k$ = 2 or 3, these recursions are very simple (there is no addition on the right-hand side) and they define the all-ones sequence (1, 1, 1, 1, 1, 1, ...). In the first nontrivial case, $k$ = 4, the defining equation is $$a_n a_{n-4} = a_{n-1} a_{n-3} + a_{n-2}^2$$ while for $k=5$ the equation is $$a_n a_{n-5} = a_{n-1} a_{n-4} + a_{n-2} a_{n-3}.$$These equations can be rearranged into the form of a recurrence relation, in which the value $a_n$ on the left hand side of the recurrence is defined by a formula on the right hand side, by dividing the formula by $a_{n-k}$. For $k=4$, this yields the recurrence $$a_n = \frac{a_{n-1} a_{n-3} + a_{n-2}^2}{a_{n-4}}$$ while for $k$ = 5 it gives the recurrence $$a_n = \frac{a_{n-1} a_{n-4} + a_{n-2} a_{n-3}}{a_{n-5}}.$$

While in the usual definition of the Somos sequences, the values of $a$_$i$ for $i$ < $k$ are all set equal to 1, it is also possible to define other sequences by using the same recurrences with different initial values.