$a_{n}$ is a sequence that $a_{1}=1,a_{2}=2,a_{3}=3$, and \[a_{n+1}=a_{n}-a_{n-1}+\frac{a_{n}^{2}}{a_{n-2}}\] Prove that for each natural $n$, $a_{n}$ is integer.
Problem
Source: Iranian National Olympiad (3rd Round) 2002
Tags: number theory proposed, number theory
01.10.2006 14:52
Omid Hatami wrote: $a_{n}$ is a sequence that $a_{1}=1,a_{2}=2,a_{3}=3$, and \[a_{n+1}=a_{n}-a_{n-1}+\frac{a_{n}^{2}}{a_{n-2}}\] Prove that for each natural $n$, $a_{n}$ is integer. Let $b_{n}=\frac{a_{n}}{a_{n}-2}+1$, we have $b_{3}=4$ and $a_{n+1}=a_{n}b_{n}-a_{n-1}, b_{n+1}=a_{n}c_{n}$, were $c_{n}=\frac{b_{n}}{a_{n-1}}$. Therefore $c_{n+1}=c_{n},c_{3}=2$, we have $b_{n+1}=2a_{n}$. It give recurent congruence: $a_{n+1}=a_{n-1}(2a_{n}-1).$ All terms are integer, because integer $a_{1},a_{2}$.
09.12.2006 09:49
i don't understand
09.12.2006 14:20
Let $b_{n}=\frac{a_{n}}{a_{n-2}}+1$, then we have $b_{3}=4$ and $a_{n+1}=a_{n}b_{n}-a_{n-1}.$ We can denote $b_{n+1}=a_{n}c_{n}$. Because $b_{n+1}=\frac{a_{n+1}}{a_{n-1}}+1=\frac{a_{n+1}+a_{n-1}}{a_{n-1}}=\frac{a_{n}b_{n}}{a_{n-1}}$, we have $c_{n}=\frac{b_{n+1}}{a_{n}}=\frac{b_{n}}{a_{n-1}}=c_{n-1}$. Therefore $c_{n+1}=c_{n}=c_{3}=2$. It give $b_{n+1}=2a_{n}$. Therefore we have recurent congruence: $a_{n+1}=a_{n}b_{n}-a_{n-1}=a_{n}2a_{n-1}-a_{n-1}=a_{n-1}(2a_{n}-1)$ or $a_{n+1}=a_{n-1}(2a_{n}-1)$. All terms are integer, because integer $a_{1},a_{2}$.