Problem 1623

To prove that for all positive integers $n$, we have $a_n < n \cdot (1 + \sqrt{2})$, we will use induction and some properties of the sequence.

1. Base Case:
For $n = 1$:
$$a_1 = 1$$
We need to check if $1 < 1 \cdot (1 + \sqrt{2})$:
$$1 < 1 + \sqrt{2}$$
Since $\sqrt{2} \approx 1.414$, it is clear that $1 < 2.414$. Thus, the base case holds.

2. Inductive Step:
Assume that for some $k \geq 1$, the inequality $a_k < k \cdot (1 + \sqrt{2})$ holds. We need to show that $a_{k+1} < (k+1) \cdot (1 + \sqrt{2})$.

By the definition of the sequence:
$$a_{k+1} = \begin{cases} a_k + 3 & \text{if } k \in \{a_1, a_2, \ldots, a_k\} \\ a_k + 2 & \text{otherwise} \end{cases}$$

We consider two cases:

- Case 1: $k \in \{a_1, a_2, \ldots, a_k\}$
$$a_{k+1} = a_k + 3$$
By the induction hypothesis:
$$a_k < k \cdot (1 + \sqrt{2})$$
Therefore:
$$a_{k+1} = a_k + 3 < k \cdot (1 + \sqrt{2}) + 3$$
We need to show:
$$k \cdot (1 + \sqrt{2}) + 3 < (k+1) \cdot (1 + \sqrt{2})$$
Simplifying the right-hand side:
$$(k+1) \cdot (1 + \sqrt{2}) = k \cdot (1 + \sqrt{2}) + (1 + \sqrt{2})$$
Thus, we need:
$$k \cdot (1 + \sqrt{2}) + 3 < k \cdot (1 + \sqrt{2}) + 1 + \sqrt{2}$$
Simplifying:
$$3 < 1 + \sqrt{2}$$
Since $\sqrt{2} \approx 1.414$, it is clear that $3 < 2.414$, which is false. Therefore, this case does not hold.

- Case 2: $k \notin \{a_1, a_2, \ldots, a_k\}$
$$a_{k+1} = a_k + 2$$
By the induction hypothesis:
$$a_k < k \cdot (1 + \sqrt{2})$$
Therefore:
$$a_{k+1} = a_k + 2 < k \cdot (1 + \sqrt{2}) + 2$$
We need to show:
$$k \cdot (1 + \sqrt{2}) + 2 < (k+1) \cdot (1 + \sqrt{2})$$
Simplifying the right-hand side:
$$(k+1) \cdot (1 + \sqrt{2}) = k \cdot (1 + \sqrt{2}) + (1 + \sqrt{2})$$
Thus, we need:
$$k \cdot (1 + \sqrt{2}) + 2 < k \cdot (1 + \sqrt{2}) + 1 + \sqrt{2}$$
Simplifying:
$$2 < 1 + \sqrt{2}$$
Since $\sqrt{2} \approx 1.414$, it is clear that $2 < 2.414$. Thus, this case holds.

Since the inductive step holds for both cases, by the principle of mathematical induction, the inequality $a_n < n \cdot (1 + \sqrt{2})$ is true for all positive integers $n$.

$\blacksquare$