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?

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

Somewhat rigorous...

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}.$$

| cite | improve this answer | |
  • $\begingroup$ Why is it only "somewhat" rigorous? $\endgroup$ – Clement C. Dec 26 '17 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.