Croatian Mathematical Competitions

Let $p_n$ be the largest prime divisor of $n^4 + n^2 + 1$ and let $q_n$ be the largest prime divisor of $n^2 + n + 1$. Then $p_n = q_{n^2}$, and from
$$n^4 + n^2 + 1 = (n^2 + 1)^2 - n^2 = (n^2 - n + 1)(n^2 + n + 1) = ((n-1)^2 + (n-1) + 1)(n^2 + n + 1)$$
it follows that $p_n = \max\{q_n, q_{n-1}\}$ for $n \ge 2$. Keeping in mind that $n^2 - n + 1$ is odd, we have
$$\gcd(n^2 + n + 1, n^2 - n + 1) = \gcd(2n, n^2 - n + 1) = \gcd(n, n^2 - n + 1) = 1.$$
Therefore, $q_n \ne q_{n-1}$.
To prove the result, it suffices to show that the set
$$S = \{n \in \mathbb{Z}_{\ge 2} \mid q_n > q_{n-1} \text{ and } q_n > q_{n+1}\}$$
is infinite, since for each $n \in S$ one has
$$p_n = \max\{q_n, q_{n-1}\} = q_n = \max\{q_n, q_{n+1}\} = p_{n+1}.$$
Suppose on the contrary that $S$ is finite. Since $q_2 = 7 < 13 = q_3$ and $q_3 = 13 > 7 = q_4$, the set $S$ is non-empty. Since it is finite, we can consider its largest element, say $m$.
Note that it is impossible that $q_m > q_{m+1} > q_{m+2} > \dots$ because all these numbers are positive integers, so there exists a $k \ge m$ such that $q_k < q_{k+1}$ (recall that $q_k \ne q_{k+1}$).
Next observe that it is impossible to have $q_k < q_{k+1} < q_{k+2} < \dots$, because
$$q_{(k+1)^2} = p_{k+1} = \max\{q_k, q_{k+1}\} = q_{k+1},$$
so let us take the smallest $l \ge k+1$ such that $q_l > q_{l+1}$. By the minimality of $l$ we have $q_{l-1} < q_l$, so $l \in S$. Since $l \ge k+1 > k \ge m$, this contradicts the maximality of $m$, and hence $S$ is indeed infinite.