En primer lugar, demostremos por inducción que $$a_{2m-1}\not\mid a_{2m}^2-1,\quad a_{2m}\not\mid a_{2m+1}^2+1\qquad (m\ge 2)\tag1$$ usando eso $$a_{n+1}\gt a_n\quad\text{and}\quad a_n\ge 3\qquad (n\ge 3)\tag2$$
(La prueba para $(2)$ está escrito al final de esta respuesta).
$(1)$ se mantiene para $m=2$ .
Supongamos que $(1)$ se mantiene para $m=2,3,\cdots, k$ .
Usando eso $$a_{2k+1}=\frac{a_{2k}^2+1}{a_{2k-1}}\implies a_{2k}^2=a_{2k-1}a_{2k+1}-1$$ tenemos que
$$\begin{align}a_{2k+2}^2-1&=\left(\frac{a_{2k+1}^2-1}{a_{2k}}\right)^2-1\\\\&=\frac{a_{2k+1}^4-2a_{2k+1}^2+1-a_{2k}^2}{a_{2k}^2}\\\\&=\frac{a_{2k+1}^4-2a_{2k+1}^2+1-(a_{2k-1}a_{2k+1}-1)}{a_{2k}^2}\\\\&=\frac{a_{2k+1}(a_{2k+1}^3-2a_{2k+1}-a_{2k-1})+2}{a_{2k}^2}\end{align}$$ no es divisible por $a_{2k+1}\ge 3$ .
Además, utilizando ese $$a_{2k+2}=\frac{a_{2k+1}^2-1}{a_{2k}}\implies a_{2k+1}^2=a_{2k}a_{2k+2}+1$$ tenemos que $$\begin{align}a_{2k+3}^2+1&=\left(\frac{a_{2k+2}^2+1}{a_{2k+1}}\right)^2+1\\\\&=\frac{a_{2k+2}^4+2a_{2k+2}^2+1+a_{2k+1}^2}{a_{2k+1}^2}\\\\&=\frac{a_{2k+2}^4+2a_{2k+2}^2+1+a_{2k}a_{2k+2}+1}{a_{2k+1}^2}\\\\&=\frac{a_{2k+2}(a_{2k+2}^3+2a_{2k+2}+a_{2k})+2}{a_{2k+1}^2}\end{align}$$ no es divisible por $a_{2k+2}\ge 3$ . $\quad\blacksquare$
Se deduce de $(1)$ que $$a_{2m+1}=\frac{a_{2m}^2\color{red}{+}1}{a_{2m-1}}\quad\text{and}\quad a_{2m+2}=\frac{a_{2m+1}^2\color{red}{-}1}{a_{2m}}$$ desde $a_{2m+1},a_{2m+2}$ tiene que ser un número entero.
Por lo tanto, tenemos $$a_{n+1}=\frac{a_n^2+(-1)^n}{a_{n-1}}\tag3$$
Por cierto, podemos demostrar por inducción que $\{a_n\}$ Satisfaciendo a $(3)$ con $a_1=1,a_2=2,a_4=12$ también satisface $$a_{n+1}=2a_n+a_{n-1}\quad (n\ge 2)\tag4$$
$(4)$ se mantiene para $n=2,3$ .
Suponiendo que $a_{n}=2a_{n-1}+a_{n-2},a_{n+1}=2a_n+a_{n-1}$ donde $n$ es incluso da $$\begin{align}a_{n+2}&=\frac{a_{n+1}^2-1}{a_{n}}=\frac{(2a_n+a_{n-1})^2-1}{a_n}=\frac{4a_n^2+4a_na_{n-1}+a_{n-1}^2-1}{a_n}\\\\&=4a_n+4a_{n-1}+\frac{a_{n-1}^2-1}{a_n}=4a_n+4a_{n-1}+\frac{a_na_{n-2}}{a_n}=4a_n+4a_{n-1}+a_{n-2}\\\\&=4a_{n}+4a_{n-1}+a_n-2a_{n-1}=5a_n+2a_{n-1}=5a_n+2(a_{n+1}-2a_n)=2a_{n+1}+a_n\end{align}$$
Suponiendo que $a_{n}=2a_{n-1}+a_{n-2},a_{n+1}=2a_n+a_{n-1}$ donde $n$ es impar da $$\begin{align}a_{n+2}&=\frac{a_{n+1}^2+1}{a_n}=\frac{(2a_n+a_{n-1})^2+1}{a_n}=\frac{4a_n^2+4a_na_{n-1}+a_{n-1}^2+1}{a_n}\\\\&=4a_n+4a_{n-1}+\frac{a_{n-1}^2+1}{a_n}=4a_n+4a_{n-1}+\frac{a_na_{n-2}}{a_n}=4a_n+4a_{n-1}+a_{n-2}\\\\&=2a_{n+1}+a_n\qquad\blacksquare\end{align}$$
De ellos se deduce que existe una única secuencia de enteros positivos $\{a_n\}$ Satisfaciendo a $$a_1=1,\quad a_2=2,\quad a_4=12,\quad a_n^2\pm 1=a_{n+1}a_{n-1}\quad (n\ge 2)$$
Por último, demostremos $(2)$ por inducción en $n$ .
$(2)$ se mantiene para $n=3$ .
Suponiendo que $a_{n+1}\gt a_n$ y $a_{n}\ge 3$ da que $$a_{n+1}\gt a_n\ge 3\quad\text{and}\quad a_{n+2}-a_{n+1}=\frac{a_{n+1}(a_{n+1}-a_n)\pm 1}{a_n}\ge\frac{3\cdot 1\pm 1}{a_n}\gt 0\qquad\blacksquare$$
