Proof that $a_{n+1}=\frac{1+a_na_{n-1}}{a_{n-2}}$ always an integer, when $a_1=a_2=a_3=1$

Question

$a_1=a_2=a_3=1$

Prove that $a_{n+1}=\frac{1+a_na_{n-1}}{a_{n-2}}$ is always an integer, when $n\ge 3$.

Bonus info: $a_n$ goes up by the same number twice in a row. For example $a_7-a_6=a_6-a_5=4$

Answer 1

Rearrange as: $$a_{n+1}a_{n-2}-a_na_{n-1}=1= a_{n}a_{n-3}-a_{n-1}a_{n-2}$$

so $$a_{n+1}a_{n-2}+a_{n-1}a_{n-2}= a_{n}a_{n-3}+a_{n}a_{n-1}$$

so $$(a_{n+1}+a_{n-1})a_{n-2}= a_{n}(a_{n-3}+a_{n-1})$$

If $b_n=a_{n+1}+a_{n-1}$ then

$$b_na_{n-2}= a_{n}b_{n-2}\implies {a_n\over a_{n-2}}={b_n\over b_{n-2}}$$ so if $n$ is even we have $${a_n\over a_2 }={b_n\over b_2}\implies 2a_n =a_{n+1}+a_{n-1}$$

So $$a_{n+1}=2a_n-a_{n-1}$$

Now the statement follows by (easy) induction.

For $n$ odd we have $${a_n\over a_3 }={b_n\over b_3}\implies 3a_n =a_{n+1}+a_{n-1}$$ So $$a_{n+1}=3a_n-a_{n-1}$$