Bulgarian Mathematical Competitions

Solution:
We shall prove by induction on $m$ that $a_{n+m} = a_{m} a_{n+1} - a_{m-1} a_{n}$ for every two positive integers $n, m \geq 2$. For $m = 2$ this is the given recurrence relation. If for some $m \geq 2$ the equality is satisfied for every $n$, then
$$\begin{aligned} a_{m+1+n} & = a_{m+(n+1)} = a_{m} a_{n+2} - a_{m-1} a_{n+1} = \\ & = a_{m} \left(a a_{n+1} - a_{n}\right) - a_{m-1} a_{n+1} = \\ & = \left(a a_{m} - a_{m-1}\right) a_{n+1} - a_{m} a_{n} = a_{m+1} a_{n+1} - a_{m} a_{n} \end{aligned}$$
which completes the induction.

The recurrence relation shows that $\gcd\left(a_{n}, a_{n-1}\right) = 1$ for every $n \geq 2$. This and $a_{n+m} = a_{m} a_{n+1} - a_{m-1} a_{n}$ imply that $\gcd\left(a_{m+n}, a_{m}\right) = \gcd\left(a_{m}, a_{n}\right)$. Using induction again we conclude that for every two positive integers $m$ and $n$ we have $\gcd\left(a_{m}, a_{n}\right) = a_{\gcd(m, n)}$. Now the assertion follows immediately: if $1 < n_{1} < n_{2} < \cdots < n_{k} < \cdots$ is an infinite sequence of relatively prime integers then $\gcd\left(a_{n_{i}}, a_{n_{j}}\right) = a_{\gcd\left(n_{i}, n_{j}\right)} = a_{1} = 1$, i.e., $a_{n_{1}}, a_{n_{2}}, \ldots, a_{n_{k}}, \ldots$ are relatively prime. Therefore the set of their prime factors is infinite.