Fedor Bakharev wrote: The sequence $a_n$ is defined by the following conditions: $a_1=1$, and for any $n\in \mathbb N$, the number $a_{n+1}$ is obtained from $a_n$ by adding three if $n$ is a member of this sequence, and two if it is not. Prove that $a_n<(1+\sqrt 2)n$ for all $n$. Using $f(n)$ as notation for $a_n$, we have : $f(1)=1$ and $f(2)=4$ $f(f(n)+1)=f(f(n))+3$ And $f(f(n)+k)=f(f(n)+k-1)+2$ $\forall k\in\{2,...,f(n+1)-f(n)\}$ And so $f(f(n)+1)=f(f(n))+3$ $f(f(n)+k)=f(f(n))+3+2(k-1)$ $\forall k\in\{2,...,f(n+1)-f(n)\}$ This implies $f(f(n+1))=f(f(n))+1+2(f(n+1)-f(n))$ and so $f(f(n+1)-2f(n+1)=f(f(n))-2f(n)+1$ And since $f(f(1))-2f(1)=-1$, we get $f(f(n))=2f(n)+n-2$ And so : $f(i)=2i+n-1$ $\forall i\in\{f(n)+1,f(n)+2,...,f(n+1)\}$ Let us prove now that $(1+\sqrt 2)(i-1)-1<f(i)<(1+\sqrt 2)i$ $\forall i\ge 1$ We'll use induction on segments $\{f(n)+1,f(n)+2,...,f(n+1)\}$ Starting situation : For $i=1$, this is $-1<f(1)<1+\sqrt 2$, true. Induction step : Let us suppose now that this is true $\forall i\in\{1,...,f(n)\}$ for some positive integer $n$ For $i\in\{f(n)+1,f(n)+2,...,f(n+1)\}$ : Since $n\in\{1,2,...,f(n)\}$ (we trivially have $f(n)\ge 2n-1\ge n$), we have $f(n)>(1+\sqrt 2)(n-1)-1$ So $\frac{n-1}{f(n)+1}<\frac 1{1+\sqrt 2}=\sqrt 2-1$ $\frac{f(i)}i=2+\frac{n-1}i$ is maximal when $i=f(n)$ and then is $2+\frac{n-1}{f(n)+1}<2+(\sqrt 2-1)=1+\sqrt 2$ And so $f(i)<(1+\sqrt 2)i$ is true $\forall i\le f(n+1)$ $\frac{f(i)+1}{i-1}=\frac{2i+n}{i-1}=2+\frac{n+2}{i-1}$ and is minimal when $i=f(n+1)-f(n)$ and is $2+\frac{n+2}{f(n+1)-f(n)-1}$ So we have to prove $2+\frac{n+2}{f(n+1)-f(n)-1}>1+\sqrt 2$, or also $\frac{f(n+1)-f(n)-1}{n+2}<1+\sqrt 2$ If $n=1$, this is $\frac{4-1-1}3<1+\sqrt 2$, true. If $n>1$ and so $n+1\le 2n-1\le f(n)$ induction hypothesis gives $f(n+1)<(1+\sqrt 2)(n+1)<(1+\sqrt 2)(n+2)+f(n)+1$. Q.E.D. And so $(1+\sqrt 2)(i-1)-1<f(i)<(1+\sqrt 2)i$ is true $\forall i\in\{1,2,...,f(n+1)\}$ End of induction step And so $\boxed{(1+\sqrt 2)(n-1)-1<a_n<(1+\sqrt 2)n\quad\forall n\in\mathbb Z_{>0}}$