Given sequence $(a_n)$ such that $a_1 = a_2 = 1$ and $$\large a_{n + 2} = 4a_{n + 1} – a_n, \forall n \ge 2$$
Prove that $$\large \exists i,j \in \mathbb N \colon \frac{a_i^2 + 2}{a_j}, \frac{a_j^2 + 2}{a_i} \in \mathbb N$$
A fundamental observation is that all numbers in the sequence are odd positive integers.
Let $\gcd(a_i, a_j) = d \ (d \ne 2)$
$$\implies \gcd(a_i, a_j – a_i^2) = d \implies \gcd(a_i, 2) = d \implies \gcd(a_i, a_j) = d = 1$$
We have that $$\left\{ \begin{align} a_j &\mid a_i^2 + 2\\ a_i &\mid a_j^2 + 2\end{align} \right. \implies \text{lcm}(a_i, a_j) \mid a_i^2 + a_j^2 + 2 \implies a_ia_j \mid a_i^2 + a_j^2 + 2$$
$$\implies a_i^2 + a_j^2 + 2 = ka_ia_j \ (k \in \mathbb N)$$
If $a_i = a_j$ then we have $a_i^2 \mid 2(a_i^2 + 1)$ and thus $a_i = a_j = 1$.
Otherwise, suppose that $1 \le a_i < a_j$ is a solution.
We know that $x_1 = a_j$ would be a solution to the quadratic equation $x^2 – ka_ix + (a_i^2 + 2) = 0$ and the other solution would be $x_2 = ka_i – a_j \ (\in \mathbb N) = \dfrac{a_i^2 + 2}{a_j} \ (< a_i)$, implying that $x_2$ is an integer and we get a smaller solution $(x_2, a_j)$.
Hence, starting with any solution $(a_i, a_j)$, we can always backtrack along with smaller solutions until $a_i = 1$.
This gives us $a_j \mid a_j^2 + 3$ or that $a_j \mid 3$. Hence $a_j = 1$, $a_j = 2$ or $a_j = 3$.
However, $a_j$ is an odd natural number $\implies a_j = 1$ or $a_j = 3$.
It can calculated that if $(a_i, a_j) = (1, 1)$ and $(a_i, a_j) = (1, 3)$, we have that $$\dfrac{a_i^2 + a_j^2 + 2}{a_ia_j} = \dfrac{1^2 + 1^2 + 2}{1 \cdot 1} = \dfrac{1^2 + 3^2 + 2}{1 \cdot 3} = 4$$
Hence, the value of $k = 4$ stays the same throughout.
Hence, we must always have $k = 4$, or that $a_i^2 + a_j^2 + 2 = 4a_ia_j \implies 4a_ia_j – (a_i^2 + a_j^2) = 2$
$$\implies \dfrac{1}{2}(a_i + a_j)^2 – \dfrac{3}{2}(a_j – a_i)^2 = 2 \implies \left(\dfrac{a_i + a_j}{2}\right)^2 – 3 \cdot \left(\dfrac{a_j – a_i}{2}\right)^2 = 1$$
Since $a_i$ and $a_j$ are odd positive integers, $x = \dfrac{a_i + a_j}{2}$ and $y = \left|\dfrac{a_j – a_i}{2}\right|$ are natural numbers.
The Pell equation $x^2 – 3y^2 = 1$ has the two nonnegative integer solutions $(x_1, y_1)$ and $(x_2, y_2)$ where $x_1 + y_1$ and $x_2 + y_2$ are respectively at their smallest and second smallest values are $(1, 0)$ and $(2, 1)$.
Consider the sequences $(x_n)$ and $(y_n)$ satisfying $$\left\{ \begin{align} x_1 = 1, x_2 = 2, x_{n + 2} &= 4x_{n + 1} – x_n\\ y_1 = 0, y_2 = 1, y_{n + 2} &= 4y_{n + 1} – y_n \end{align} \right. \ (n \in \mathbb Z^+, n \ge 2)$$
There exists $m \in \mathbb Z^+$ such that $(x, y) = (x_m, y_m)$
$\implies (a_i, a_j)$ is a permutation of $(x_m + y_m, x_m – y_m)$. Let $\left\{ \begin{align} u_n = x_n + y_n\\ v_n = x_n – y_n \end{align} \right. \ (n \in \mathbb Z^+)$.
We have that
$$\left\{ \begin{align} u_1 = 1, u_2 = 3, u_{n + 2} &= 4u_{n + 1} – u_{n}\\ v_1 = 1, v_2 = 1, v_{n + 2} &= 4v_{n + 1} – v_n \end{align} \right. \implies u_{n – 1} = v_n = a_n \ (n \in \mathbb Z^+, n \ge 2)$$
Then I don't know what to do next. Great.
Best Answer
The condition holds true for all pairs $a_i, a_{i+1}$.
In fact, the relation $a_i^2+2=a_{i-1}a_{i+1}$ holds for all $i$, from which the above result follows.
This can be proven by induction. Assume $a_i^2+2=a_{i-1}a_{i+1}$ is true for $1<i<n$. That makes $$ \begin{split} a_{n-1}a_{n+1} & = a_{n-1}\cdot(4a_n-a_{n-1}) = 4a_{n-1}a_n-a_{n-1}^2 \\ & = 4a_{n-1}a_n-(a_{n-2}a_n-2) = (4a_{n-1}-a_{n-2})\cdot a_n + 2 \\ & = a_n^2 + 2 \end{split} $$ for $n>2$, and you just have to verify that the relation holds for $i=2$ which is the first case not covered by the induction step.