Bulgarian Mathematical Olympiad 1987

First note that $(x_n)_{n\ge 2}$ is strictly increasing, as can be seen from $$ x_{n+2} = 9 x_{n+1} + (x_{n+1}-x_n) + 4(x_{n+1}-1) \, . $$

Now – inspired by How do I prove that the recurrence contains no perfect square? – we consider the quadratic form $$ Q(x, y) = x^2 - 14xy + y^2 + 4x + 4y + 4 \, . $$ $Q$ is chosen such that $ Q(x_{n+1}, x_n)$ an invariant: $$ Q(x_{n+2}, x_{n+1}) = Q(14x_{n+1}-x_n-4, x_{n+1}) = Q(x_{n+1}, x_n) \, , $$ and since $Q(x_2, x_1) = Q(1,1) = 0$ we have $$ Q(x_{n+1}, x_n) = 0 $$ for $n = 1, 2, 3, \ldots$ . Then also $$ Q(x_{n+1}, x_{n+2}) = 0 $$ because of the symmetry, which means that $y=x_n$ and $y=x_{n+2}$ are (distinct) solutions of the quadratic equation $$ 0 = Q(x_{n+1}, y) = y^2 + (4-14 x_{n+1})y + (x_{n+1}+2)^2 \, . $$ Using Vieta's formulas it follows that $$ x_n \cdot x_{n+2} = (x_{n+1}+2)^2 $$ for all $n$, so that $x_{n+2}$ is a perfect if $x_n$ is. And since $x_1$ and $x_2$ are perfect squares, it follows that all $x_n$ are perfect squares.

---

Remark: $x_n = 1, 1, 9, 121, 1681, 23409, 326041, 4541161, \ldots$ is (apart from the initial element) the sequence A046184 in the On-Line Encyclopedia of Integer Sequences®:

A046184 Indices of octagonal numbers which are also square.