# Recurrence Relation involving Fractional Part

I am considering the following sequence: $$a_0=\sqrt 2$$ $$a_{n+1}=a_n+\{a_n\}$$ where $\{x\}:= x-\lfloor x\rfloor$ denotes the fractional part function. Since I have observed that the sequence exhibits almost-linear growth, I am trying to find the value of the limit $$\lim_{n\to\infty} \frac{a_n}{n}$$ This is by no means rigorous, but I believe that the value is $1/2$, because the $\{a_n\}$ seems to behave somewhat like a random variable, and if we instead considered the sequence $$b_{n+1}=b_n+X_n$$ where each $X_n$ is a random variable uniformly distributed in $(0,1)$, the expected value of $\Delta b_n=X_n$ is $1/2$.

Any ideas about how to prove this more rigorously? Is my reasoning even correct?

• Hi, so sorry but what does $\{a_n\}$ means in this context? – Karn Watcharasupat Dec 23 '17 at 17:06
• @KarnWatcharasupat Oh, sorry, I should have clarified. It denotes the fractional part of $a_n$: $$\{a_n\}:= a_n-\lfloor a_n\rfloor$$ – Franklin Pezzuti Dyer Dec 23 '17 at 17:11

Let $\lfloor a_n \rfloor = I_n$, $\{a_n\} = f_n$.The problem can be decomposed into \begin{align} f_{n+1} &= 2f_n - \mathbb{1}_{f_n \geq \frac{1}{2}} \\ I_{n+1} &= I_n + \mathbb{1}_{f_n \geq \frac{1}{2}} \end{align} The fractional part follows a Bernoulli map, whose invariant density is the uniform distribution if $f_0$ is irrational, so that $$\lim_{n\to \infty} \frac{1}{n}\sum_{k=1}^n\mathbb{1}_{f_k \geq \frac{1}{2}} = \frac{1}{2}.$$ Therefore $$\lim_{n\to \infty} \frac{a_n}{n}= \lim_{n\to \infty} \frac{I_n}{n} =\lim_{n\to \infty} \frac{1}{n}\sum_{k=1}^n\mathbb{1}_{f_k \geq \frac{1}{2}} = \frac{1}{2}.$$