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)
Problem
Source: 2021 Czech-Polish-Slovak Match, P5
Tags:
timon92
03.08.2021 13:21
$a_n = \left\lfloor (1+\sqrt 2)n -\frac{\sqrt 2}{2}\right\rfloor$
also, see A086377
MathHorse
17.04.2022 02:15
A good idea is to show the stricter condition $(n-1)(\sqrt{2}+1)<a_n<n(\sqrt{2}+1)$. Let $f(n)$ be the number of elements of the sequence smaller than $n$. It is easy to see that $a_n=2n-1+f(n)$. Use induction. The main idea is $a_{\lfloor n(\sqrt{2}-1)\rfloor}<\lfloor n(\sqrt{2}-1)\rfloor(\sqrt{2}+1)<n(\sqrt{2}-1)(\sqrt{2}+1)=n$ by the induction hypothesis, so $f(n)\geq\lfloor n(\sqrt{2}-1)\rfloor$. A similar argument for the other direction is enough to complete the induction step.
NO_SQUARES
15.12.2023 16:46
It was on 239 Open Mathematical Olympiad 2018! https://artofproblemsolving.com/community/c6h3045605p27431382