Problem 3

We define a sequence of real numbers $a_{1}, a_{2}, a_{3}, \ldots$ by $a_{1}=3 / 2$, then

$$
a_{n+1}=1+\frac{n}{a_{n}}
$$

for all integers $n \geqslant 1$.

Find an integer $k \geqslant 1$ such that $2020 \leqslant a_{k}<2021$.

## §
Solution

We will prove by induction on $n \geqslant 1$ the property $P_{n}$ as follows:

$$
\sqrt{n}<a_{n}<\sqrt{n}+1
$$

First, since $a_{1}=3 / 2$, we observe that $P_{1}$ is true. Then, if $n \geqslant 1$ is an integer such that $P_{n}$ is true, we have

$$
1+\frac{n}{\sqrt{n}+1}<a_{n+1}<\sqrt{n}+1<\sqrt{n+1}+1
$$

Thus, we deduce $P_{n+1}$ from the fact that

$$
\begin{aligned}
1+\frac{n}{\sqrt{n}+1} & =1+\frac{(\sqrt{n}+1)(\sqrt{n}-1)+1}{\sqrt{n}+1}=\sqrt{n}+\frac{1}{\sqrt{n}+1} \\
& =\sqrt{n+\frac{2 \sqrt{n}}{\sqrt{n}+1}+\frac{1}{(\sqrt{n}+1)^{2}}} \geqslant \sqrt{n+\frac{\sqrt{n}+1}{\sqrt{n}+1}}=\sqrt{n+1}
\end{aligned}
$$

We conclude in particular that $2020<a_{2020^{2}}<2021$: it is therefore sufficient to choose $k=2020^{2}$.

## $\S$ Remark

By calculating the first few terms of the sequence $a_{1}, a_{2}, a_{3}, \ldots$, one might be led to formulate the (correct) conjecture that this sequence is strictly increasing. It is then easy to show that this conjecture is in fact equivalent to the fact that $v_{n-1}<a_{n}<v_{n}$ for all integers $n \geqslant 1$, where we have set $v_{n}=\sqrt{n+1 / 4}+1 / 2$. Finally, we can prove this double inequality with a proof similar to the one presented above, although much more technical. Consequently, the suitable integers $k$ are those such that $4078381 \leqslant k \leqslant 4082420$.

## $\square$