Note that $a_{n+2} = 4a_{n+1} - a_n$, which can be easily proved by induction. Also, I think this problem was made based on famous vieta jumping example; $\frac{x^2 + y^2 +2}{xy} \in \mathbb{Z}$

Can someone check this solution? Claim 1) $a_n>0$ for all $n\ge 0$. Proof) Prove $a_{n+1}>a_n$ by induction. Main Claim) $a_{n}\in\mathbb{Z}$ for all $n\ge 0$. Proof) Check $a_1, a_2$ manually. By induction, suppose $a_0, \dots, a_{n+1}$ are integers. Thus, $a_n=\frac{a_{n-1}^2+2}{a_{n-2}}$ is an integer. Then, $ 2+a_{n-1}^2\equiv 0\pmod {a_n}$ Then, $ 2^2+2a_{n-1}^2\equiv 0\pmod {a_n}$ Then, $ (a_n^2+2)^2+2a_{n-1}^2\equiv 0\pmod {a_n}$ Then, $a_{n+1}^2+2\equiv ((a_n^2+2)/a_{n-1})^2+2\equiv 0\pmod {a_n}$

invt wrote: Claim 2) $2\nmid a_n$ for all $n\ge 0$ Proof) Trivial. What does it even mean to state this before proving that $a_n$ is an integer?

Tintarn wrote: invt wrote: Claim 2) $2\nmid a_n$ for all $n\ge 0$ Proof) Trivial. What does it even mean to state this before proving that $a_n$ is an integer? Is it ok now?

Let us use Induction. Suppose $a_{0},a_{1},\cdots ,a_{k+1}$ are integers, We will prove $a_{k+2}$ is also an integer. Base Case: When $k=0$, We can easily find $a_{2}=\frac{a_{1}^{2}+2}{a_0}=11$ In the same way, when $k=1$, We can find $a_{3}=\frac{a_{2}^{2}+2}{a_1}=41$ Inductive Step: ($k\ge 2$) $a_{k+2}=\frac{a_{k+1}^{2}+2}{a_k}=\frac{(\frac{a_k^2+2}{a_{k-1}})^{2}+2}{a_k}=\frac{(a_k^{2}+2)^2+2a_{k-1}^2}{a_k\cdot a_{k-1}^2}$ (1) $a_k|(a_k^2+2)^2+2a_{k-1}^2 \Rightarrow a_k|4+2a_{k-1}^2$ which is true by, $\frac{a_{k-1}^2+2}{a_{k}}=a_{k-2}$ and $a_{k-2}$ is an integer. (2) $a_{k-1}^{2}|(a_k^2+2)^2+2a_{k-1}^2 \Rightarrow a_{k-1}^{2}|(a_{k}^2+2)^2$ which is true by, $\frac{a_{k}^2+2}{a_{k-1}}=a_{k+1}$ and $a_{k+1}$ is an integer. Therefore, $a_{k+2}$ is an integer. Hence, we're done!

Note that $a_{n+2} = 4a_{n+1} - a_n$, prove it by induction and prove the initial claim by induction as well.

mathverse06 wrote: Let us use Induction. Suppose $a_{0},a_{1},\cdots ,a_{k+1}$ are integers, We will prove $a_{k+2}$ is also an integer. Base Case: When $k=0$, We can easily find $a_{2}=\frac{a_{1}^{2}+2}{a_0}=11$ In the same way, when $k=1$, We can find $a_{3}=\frac{a_{2}^{2}+2}{a_1}=41$ Inductive Step: ($k\ge 2$) $a_{k+2}=\frac{a_{k+1}^{2}+2}{a_k}=\frac{(\frac{a_k^2+2}{a_{k-1}})^{2}+2}{a_k}=\frac{(a_k^{2}+2)^2+2a_{k-1}^2}{a_k\cdot a_{k-1}^2}$ (1) $a_k|(a_k^2+2)^2+2a_{k-1}^2 \Rightarrow a_k|4+2a_{k-1}^2$ which is true by, $\frac{a_{k-1}^2+2}{a_{k}}=a_{k-2}$ and $a_{k-2}$ is an integer. (2) $a_{k-1}^{2}|(a_k^2+2)^2+2a_{k-1}^2 \Rightarrow a_{k-1}^{2}|(a_{k}^2+2)^2$ which is true by, $\frac{a_{k}^2+2}{a_{k-1}}=a_{k+1}$ and $a_{k+1}$ is an integer. Therefore, $a_{k+2}$ is an integer. Hence, we're done! $\frac{a_{k-1}^2+2}{a_{k}}$ is not $a_{k-2}$, check out the problem again I made the same mistake too lol

From $a_{n+2} = \frac{a_{n+1}^2 + 2}{a_n}$ we get that $a_{n+1}^2 + 2 = a_n.a_{n+2}$ $\Rightarrow$ $a_{n+1}^2 - a_n.a_{n+2} = -2$. Similarly we get that $a_n^2 - a_{n-1}.a_{n+1} = -2$ $\Rightarrow$ we have that $a_{n+1}^2 - a_n.a_{n+2} = a_n^2 - a_{n-1}.a_{n+1}$ for each n, which is equivalent to $a_n^2 + a_n.a_{n+2} = a_{n+1}^2 + a_{n+1}.a_{n-1}$ or simply $\frac{a_{n+2}+a_n}{a_{n+1}} = \frac{a_{n+1}+a_{n-1}}{a_n}$ for each n $\Rightarrow$ if $f(n) = \frac{a_{n+1}+a_{n-1}}{a_n}$, then f(n) must be a constant. Since we check that $a_0 = 1$, $a_1 = 3$, $a_2 = 11$, $a_3 = 41$, we have that f(1) = 4 and f(2) = 4 $\Rightarrow$ f(n) = 4 $\Rightarrow$ $4a_n = a_{n+1} + a_{n-1}$ or just $a_{n+1} = 4a_n - a_{n-1}$ so for the sequence we get the recurrence $a_{n+2} = 4a_{n+1} - a_n$. Now its obvious that every $a_i$ is an integer, since $a_{i-1}$ and $a_{i-2}$ are integers. From this recurrence, using the characteristic polynomial for it we get that the closed form for this recurrence is $a_n = (\frac{3 + \sqrt{3}}{6})(2 + \sqrt{3})^n + (\frac{3 - \sqrt{3}}{6})(2 - \sqrt{3})^n$, which is obviously positive $\Rightarrow$ we proved that for all nonnegative integer n, $a_n$ is a positive integer. We are ready.

Provable easily by strong induction, interesting problem

Note that \begin{align*} a_{n+2}a_n - a_{n+1}^2 = a_{n+1}a_{n-1} - a_n^2 = 2 \quad \longrightarrow \quad \dfrac{a_{n+2}+a_n}{a_{n+1}} = \dfrac{a_{n+1}+a_{n-1}}{a_n}. \end{align*}Since $a_0 = 1$, $a_1 = 3$, and $a_2 = 11$, then we may compute $a_{n+1} = 4a_n - a_{n-1}$. Thus, all terms of the sequence are positive integers.

wait the recurrence is exactly the same as the amount of ways to tile a $3 \times n$ rectangle with $2 \times 1$ dominoes :flushed: it would be interesting if there was a good reason for this We prove that $4a_{n-1}-a_{n-2}=a_n$ with induction. For the base case, we have $4(1)-1=3$, which is clearly true. For the inductive step, we assume that this is true for $n-1$ and plug it into the recurrence for $n$, giving \[\frac{(4a_{n-2}-a_{n-3})^2+2}{a_{n-2}}=a_n\]\[\implies 16a_{n-2}-8a_{n-3}+\frac{a_{n-3}^2+2}{a_{n-2}}=a_n\]at which point we can substitute $16a_{n-2}-4a_{n-3}=a_{n-1}$ so now we need to prove that \[4a_{n-3}-\frac{a_{n-3}^2+2}{a_{n-2}}=a_{n-2},\]and then we can use the inductive hypothesis again to get that we need $\frac{a_{n-3}^2+2}{a_{n-2}}=a_{n-4}$, which is true, so we are done.