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

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.

• Let $f(p,q)$ be the limit of the sequence when $a_1=p/q$; then I believe that for fixed $p$, the function $g_p(q) = f(p,q)$ is periodic with period $p$, while for fixed $q$, the function $h_q(p) = f(p,q)$ is periodic with period lcm$[1,2,\dots,q]$. Jul 23, 2013 at 8:25
• Greg's belief is correct: for fixed $p$, if $q=pk+r$ with $k\ge 0$ and $0<r<p$ then the $a_n$ sequence begins $p/q,p/(q-p),p/(q-2p),...,p/(q-kp)=p/r$, so indeed the limit is determined by $p$ and $r$. If $q$ is fixed, and $p$ and $P$ are congruent to one another mod lcm$(1,2,...,q)$, then $p$ and $P$ are congruent to one another modulo any integer between $1$ and $q$, so they're congruent mod $q_n$ for all $n$. Thus the sequences of $q_n$'s and $r_n$'s for $a_1=p/q$ are identical to the corresponding sequences for $a_1=P/q$. Aug 20, 2013 at 18:55
• Greg's functions $g_p$ seems to be surjective as a function on $\{1,\ldots, p\}$ into the divisors of $p$. Aug 22, 2013 at 11:55
• So where is the question here? Aug 22, 2013 at 16:33
• @Norbert. The second sentence from the end looks like a question to me (though a bit open-ended, I'll admit). Aug 22, 2013 at 16:51

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

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

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.

• It is stated at the beginning of the question that $a_1$ is rational (I guess this was changed to $a_0$ later). Aug 22, 2013 at 17:44
• @JonasMeyer Thanks for pointing out the mistake in the question...changed the $a_1$ to $a_0$. Aug 22, 2013 at 18:00
• how to show this is not convergent for irrational starting point? i have shown this seq is increasing so it must not be bounded above. Feb 25, 2019 at 12:54