Consider the following recurrence, $$a_n=\frac{4a_{n-1}^3+2a_{n-1}-a_{n-2}}{1+4a_{n-1}a_{n-2}}$$ where $a_0=0, a_1=1$.
(a) Show that every $a_n$ is an integer.
(b) Find the general term of $a_n$.
What I've done: I've calculated some values: $$a_2=6, a_3=35, a_4=204, a_5=1189, a_6=6930, a_7=40391,\\ a_8=235416, a_9=1372105, \ldots $$
I also tried to find the condition to make the value of fraction integer, but I was stuck since the formula is about cubic polynomial and I don't know how to deal with it.
Best Answer
Based on Gary's comment re: the sequence of values are the same as in the OEIS A001109, for $n \ge 2$, define
$$f(n) = a_n - 6a_{n-1} + a_{n-2} \tag{1}\label{eq1A}$$
Note $f(2) = a_2 - 6a_1 + a_0 = 6 - 6(1) + 0 = 0$. Assume $f(k) = 0$ for some integer $k \ge 2$. Using the recursion formula for just $a_k$, this means
$$\begin{equation}\begin{aligned} 0 & = f(k) \\ & = a_k - 6a_{k-1} + a_{k-2} \\ & = \frac{4a_{k-1}^3+2a_{k-1}-a_{k-2}}{1+4a_{k-1}a_{k-2}} + (-6a_{k-1} + a_{k-2}) \\ & = \frac{4a_{k-1}^3+2a_{k-1}-a_{k-2} + (-6a_{k-1} + a_{k-2})(1+4a_{k-1}a_{k-2})}{1+4a_{k-1}a_{k-2}} \\ & = \frac{4a_{k-1}^3+2a_{k-1}-a_{k-2} - 6a_{k-1} - 24a_{k-1}^{2}a_{k-2} + a_{k-2} + 4a_{k-1}a_{k-2}^2}{1+4a_{k-1}a_{k-2}} \\ & = \frac{4a_{k-1}^3 - 4a_{k-1} - 24a_{k-1}^{2}a_{k-2} + 4a_{k-1}a_{k-2}^2}{1+4a_{k-1}a_{k-2}} \\ & = \frac{4a_{k-1}(a_{k-1}^2 - 1 - 6a_{k-1}a_{k-2} + a_{k-2}^2)}{1+4a_{k-1}a_{k-2}} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$
Thus, either $a_{k-1} = 0$, or
$$a_{k-1}^2 - 1 - 6a_{k-1}a_{k-2} + a_{k-2}^2 = 0 \tag{3}\label{eq3A}$$
The first case of $a_{k-1} = 0$ is not possible since $a_{2} = 1$ and it's fairly easy to prove that $a_{n}$ is a strictly increasing positive sequence for $n \ge 1$. Starting with $a_1 \gt a_0$ then, for $n \ge 2$, with $a_{n-1} \gt a_{n-2} \;\to\; 4a_{n-1}^2 + 1 \gt 4a_{n-1}a_{n-2} + 1$, we get from the recurrence sequence that
$$\begin{equation}\begin{aligned} a_n & = \frac{4a_{n-1}^3+a_{n-1}+(a_{n-1}-a_{n-2})}{1+4a_{n-1}a_{n-2}} \\ & \gt \frac{4a_{n-1}^3+a_{n-1}}{1+4a_{n-1}a_{n-2}} \\ & = a_{n-1}\left(\frac{4a_{n-1}^2+1}{4a_{n-1}a_{n-2}+1}\right) \\ & \gt a_{n-1} \end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Thus, this means that \eqref{eq3A} must hold. Next, checking $f(k+1)$ in \eqref{eq1A}, we get the same end result as the last line of \eqref{eq2A}, but with all of the indices increased by $1$, i.e.,
$$f(k + 1) = \frac{4a_{k}(a_{k}^2 - 1 - 6a_{k}a_{k-1} + a_{k-1}^2)}{1+4a_{k}a_{k-1}} \tag{5}\label{eq5A}$$
From the second line of \eqref{eq2A} we have $a_k = 6a_{k-1} - a_{k-2}$, so substituting that into the expression in the brackets in the numerator gives, using \eqref{eq3A}, that
$$\begin{equation}\begin{aligned} & a_{k}^2 - 1 - 6a_{k}a_{k-1} + a_{k-1}^2 \\ & = (6a_{k-1} - a_{k-2})^2 - 1 - 6(6a_{k-1} - a_{k-2})a_{k-1} + a_{k-1}^2 \\ & = 36a_{k-1}^2 - 12a_{k-1}a_{k-2} + a_{k-2}^2 - 1 - 36a_{k-1}^2 + 6a_{k-1}a_{k-2} + a_{k-1}^2 \\ & = -6a_{k-1}a_{k-2} + a_{k-2}^2 - 1 + a_{k-1}^2 \\ & = 0 \end{aligned}\end{equation}\tag{6}\label{eq6A}$$
This means that $f(k+1) = 0$. Thus, by induction, $f(n) = 0$ for all $n \ge 2$, i.e.,
$$a_n = 6a_{n-1} - a_{n-2} \tag{7}\label{eq7A}$$
Since $a_0$ and $a_1$ are integers, then all $a_n$ are integers.
For the second part, note that \eqref{eq7A} is an example of a Linear recurrence with constant coefficients. From it's General solution section, the characteristic polynomial is
$$p(\lambda) = \lambda^2 - 6\lambda + 1 = 0 \tag{8}\label{eq8A}$$
The roots are
$$\lambda = \frac{6\pm\sqrt{36-4}}{2} = 3\pm 2\sqrt{2} \tag{9}\label{eq9A}$$
so, since they are distinct, the general solution is
$$a_n = c_1(3 + 2\sqrt{2})^n + c_2(3 - 2\sqrt{2})^n \tag{10}\label{eq10A}$$
for appropriate constants $c_1$ and $c_2$. To determine them, use that $a_0 = 0$ to get
$$c_1 + c_2 = 0 \;\;\to\;\; c_2 = -c_1 \tag{11}\label{eq11A}$$
Using this and $a_1 = 1$ gives
$$c_1(3 + 2\sqrt{2}) - c_1(3 - 2\sqrt{2}) = 1 \;\to\; 4c_1\sqrt{2} = 1 \;\to\; c_1 = \frac{1}{4\sqrt{2}} \tag{12}\label{eq12A}$$
Using this and \eqref{eq11A} in \eqref{eq10A}, the general form of $a_n$ is
$$a_n = \frac{(3 + 2\sqrt{2})^n - (3 - 2\sqrt{2})^n}{4\sqrt{2}} \tag{13}\label{eq13A}$$