Consider the following sequence: let $a_0>0$ be rational. Define $$a_{n+1}= \frac{a_n}{1-\{a_n\}},$$ 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 $$a_{n+1} = \frac{p_n/q_n}{1-r_n/q_n} = \frac{p_n}{q_n – r_n},$$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.
Best Answer
Wanted to record some observations here...
If we consider the sequence
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...