Limit of recursive sequence $a_{n+1} = \frac{a_n}{1- \{a_n\}}$

Question

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.

Answer 1

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

Answer 2

Let $n\in\Bbb N$, $q_i$ for $0\leq i\leq n$ be a non-decreasing sequence of positive integers and \begin{align} &a_0=\left(\sum_{j=0}^n\frac 1{q_0\cdots q_j}\right)^{-1}& &a_{i+1}=\frac{a_i}{1-\{a_i\}} \end{align} Then $a_i=q_n$ for every $i\geq n$.

This follows by proving, by induction, that for every $i\leq n$ we have $$a_i=\left(\sum_{j=i}^n\frac 1{q_i\cdots q_j}\right)^{-1}\tag 1$$ This is clearly true for $i=0$. Assuming $(1)$, then clearly $a_i\leq q_i$. On the other hand, $j\geq i$ implies $q_j\geq q_i>1$ (the case $q_i=1$ is trivial), hence $$\frac 1{a_i}\leq\sum_{j=i}^n\frac 1{q_i^{j+1}}<\frac 1{q_i-1}$$ from which $q_i-1<a_i\leq q_i$ that's $\lceil a_i\rceil=q_i$. Consequently, \begin{align} a_{i+1} &=\frac{a_i}{1-\{a_i\}}\\ &=\frac{a_i}{q_i-a_i}\\ &=\left(\sum_{j={i+1}}^n\frac1{q_{i+1}\cdots q_j}\right)^{-1}\\ \end{align} hence the assertion follows by induction on $i$.

Answer 3

Your proof is correct if a0 is rational number. It will not converge for irrational numbers like e or pi. Assuming rationality, I don't think there is a closed form solution of converging number (until and unless you embed loop and conditional kind of behavior in closed form). There is equivalence class of converging point given q0 where solution will converge: the equivalence class are factors (I mean all factors not only prime factors) of p0 including itself. Therefore, if p0 is prime it will converge to itself.