# Limit of recursive sequence an+1=an1−{an}a_{n+1} = \frac{a_n}{1- \{a_n\}}

Consider the following sequence: let $a_0>0$ be rational. Define where $\{a_n\}$ is the fractional part of $a_n$ (i.e. $\{a_n\} = a_n - \lfloor a_n\rfloor$). Show that $a_n$ converges, and find its limit.

We can show it converges as follows: suppose $a_n = p_n/q_n = k_n + r_n/q_n$, where $p_n = k_nq_n + r_n$, $0 \leq r_n < q_n$. Then so the denominator will keep decreasing until it is a divisor of $p_0$ (maybe 1). Also, note we may take $p_n = p_0$ for all $n$.

Further, the limit will be $\leq \frac{p_0}{\operatorname{gcf}{(p_0,q_0)}}$, because if $f \mid p_0$ and $f\mid q_n$, then $f\mid (p_0 - k_nq_n)=r_n$, so $f \mid q_n - r_n = q_{n+1}$. But the limit may be strictly smaller; for instance, $a_0 = 30/7$ converges right away to 6.

Can we say anything else about the limit of a sequence starting with $a_0$? This was a problem on a qualifier, so I suspect there is more to the answer, but maybe not.

Wanted to record some observations here...

If we consider the sequence

• $p = a_1 q + r_1$
• $p = a_2(q-r_1) + r_2$
• $p = a_3(q-r_1-r_2) + r_3$
• etc.

and try to solve for the remainders in the form $r_i = c_i p - d_i q$, there is a nice recursive relation:

First, $c_1 = 1$ and $d_1 = a_1$, and in general,

$c_j = 1 + a_j (c_1 + \ldots + c_{j-1})$ and
$d_j = (1+a_1)(1+a_2)\cdots (1+a_{j-1})a_j$

We can also write $c_j(1+a_j) = c_1 + \ldots + c_j$ so that
$c_j = 1 + \frac{a_j}{a_{j-1}}(c_{j-1} (1+a_{j-1})-1)$. This can be expanded further to obtain the form

$c_j = 1 + a_j [ 1 + (1+a_{j-1}) [ 1 + (1+a_{j-2}) [ 1 + \ldots [1 + (1+a_2)]]\ldots]$, or even

$c_j = 1+a_j + a_j(1+a_{j-1}) + a_j(1+a_{j-1})(1+a_{j-2}) + \ldots + a_j(1+a_{j-1})(1+a_{j-2})\cdots(1+a_2)$

Note that the $a_i$ are strictly increasing in the sequence. Suppose the procedure terminates at the $n$-th step (when $r_n=0$). The limit is then $p/a_n$, and $0 = r_n = c_n (p/q) - d_n$ or that $p/q = d_n / c_n$.

I still don't have a closed form expression, but for instance:

For rationals $p/q$ for which the sequence terminates in the first step, $0 = r_1 = c_1 (p/q) - d_1 = p/q - a_1$, so that $q$ is a divisor of $p$, and the limit is $p/q$.

For termination at the second step, $0 = r_2 = c_2 (p/q) - d_2 = (1+a_2)(p/q) - (1+a_1)a_2$, or that $\frac{p}{q} = \frac{(1+a_1)a_2}{1+a_2}$. If there exists $a_1 < a_2$ satisfying this equality, then the sequence terminates in the second step. One such criteria is if $d$ is a divisor of $p$, $q = d+1$ and $p/d - 1 < d$, then the sequence terminates in the second step to $p/d = (1+a_1)$.

For examples: $30/7 = (1+4)6/(1+6)$. Also, $30/4 = 120/16 = (1+7)15/(1+15)$.

Third step termination: $\frac{p}{q} = \frac{ (1+a_1)(1+a_2)a_3 }{ 1 + a_3(1+(1+a_2)) }$, limit is $(1+a_1)(1+a_2)$, and etc.

Also, it appears that if you plug in $a_n = d$ in any formula, you can generate for which $p$ the process converges to $d$ by substituting any $a_1 < a_2 < \ldots < a_{n-1} < d$. Maybe there's more special structure...