The sequence $ a_n$ is defined as follows: $ a_0=1, a_1=1, a_{n+1}=\frac{1+a_{n}^2}{a_{n-1}}$. Prove that all the terms of the sequence are integers.
Problem
Source: recursive sequence, prove that the terms are integers
Tags: induction, algebra proposed, algebra
mszew
05.11.2008 15:57
Lets prove by induction that $ a_n=F_{2n-1}$ for $ n\ge 2$ with $ F_i$ the fibonacci sequence $ F_0=0$ and $ F_1=1$ and $ F_{n+1}=F_n+F_{n-1}$ for $ n>1$. $ a_2=F_3=2$ and $ a_3=F_5=5$ given that $ a_{n-1}=F_{2(n-1)-1}$ and $ a_n=F_{2n-1}$ then: $ a_{n + 1} = \frac {1 + a_{n}^2}{a_{n - 1}}=\frac {1 + F_{2n-1}^2}{F_{2n - 3}}$ $ a_{n + 1} = \frac {1 + (F_{2n-2}+F_{2n-3})^2}{F_{2n - 3}}$ $ a_{n + 1} = F_{2n-3}+2F_{2n-2}+{\frac {1 + F_{2n-2}^2}{F_{2n - 3}}}$ Using Cassiny's identity: $ a_{n + 1} = F_{2n-1}+F_{2n-2}+{\frac {F_{2n-1} F_{2n-3}}{F_{2n - 3}}}$ $ a_{n + 1} =F_{2n}+F_{2n-1}$ $ a_{n + 1} =F_{2n+1}$ $ a_{n + 1} =F_{2(n+1)-1}$
The QuattoMaster 6000
06.11.2008 03:57
bambaman wrote: The sequence $ a_n$ is defined as follows: $ a_0 = 1, a_1 = 1, a_{n + 1} = \frac {1 + a_{n}^2}{a_{n - 1}}$. Prove that all the terms of the sequence are integers.
We proceed with induction. $ a_{2}=2$, so $ a_2$ is an integer (as are $ a_0$ and $ a_1$). Now, assume that $ a_i$ is an integer for $ 1\le i\le n$. We have that $ a_{n+1}=\frac{1+(\frac{a_{n-1}^2+1}{a_{n-2}})^2}{a_{n-1}}$. Upon multiplying out, we have that $ a_{n+1}=\frac{a_{n-2}^2+a_{n-1}^4+2a_{n-1}^2+1}{a_{n-2}^2a_{n-1}}$. Now, $ a_{n-1}$ and $ a_{n-2}$ are coprime since $ a_{n-1}^2+1=a_{n-2}a_n$. Thus, it suffices to show that $ a_{n-2}^2|(a_{n-2}^2+a_{n-1}^4+2a_{n-1}^2+1)$ (which is clearly true since $ a_{n-2}^2|(a_{n-1}^2+1)^2$) and $ a_{n-1}|(a_{n-2}^2+a_{n-1}^4+2a_{n-1}^2+1)$ (which is clearly true since $ a_{n-1}|(a_{n-2}^2+1)$). Since both are proven, $ a_{n+1}$ is an integer, so induction is complete.
me@home
09.11.2008 23:40
Together, \[ a_{n+1}a_{n-1}=1+a_n^2\wedge a_{n+2}a_{n}=1+a_{n+1}^2\implies \frac{a_{n+1}}{a_n}=\frac{a_{n+2}+a_n}{a_{n+1}+a_{n-1}}\] Telescoping, we find that \[ a_{n+1}=\frac{a_{n+2}+a_n}{3}\iff a_{n+2}=3a_{n+1}-a_n\] hence the conclusion.
viperstrike
20.07.2014 21:09
It suffices to show that $a_{n+1}=3a_n-a_{n-1}$ for $n \ge 2$. This holds for $n=2$ and assume it holds for $n$. Then $a_{n+1}a_{n-1}=1+a_n^2$ $a_{n+1}(3a_n-a_{n+1})=1+a_n^2$ $3a_{n+1}-a_n=(1+a_{n+1}^2)/a_n$ $3a_{n+1}-a_n=a_{n+2}$ as desired.
MuradSafarli
02.01.2025 16:10
After a few substitutions, we get that there is a connection between the limits of the sequence and the Fibonacci sequence. Let 1=F1, 1=F2, 2=F3 and we get ak=F2k-1. Then we can finish the question by induction.