CAPS 2021 Problem 5

The sequence $a_1, a_2, a_3, \ldots$ satisfies $a_1=1$ , and for all $n \ge 2$ , it holds that $$a_n= \begin{cases} a_{n-1}+3 ~~ \text{if} ~ n-1 \in \{ a_1,a_2,\ldots,,a_{n-1} \} ; a_{n-1}+2 ~~ \text{otherwise}. \end{cases}$$ Prove that for all positive integers n, we have $$a_n < n \cdot (1 + \sqrt{2}).$$

Dominik Burek (Poland) (also known as Burii)