30
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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]$. $\endgroup$ – Greg Martin Jul 23 '13 at 8:25
  • $\begingroup$ 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$. $\endgroup$ – Michael Zieve Aug 20 '13 at 18:55
  • $\begingroup$ Greg's functions $g_p$ seems to be surjective as a function on $\{1,\ldots, p\}$ into the divisors of $p$. $\endgroup$ – Uwe Stroinski Aug 22 '13 at 11:55
  • $\begingroup$ So where is the question here? $\endgroup$ – Norbert Aug 22 '13 at 16:33
  • 1
    $\begingroup$ @Norbert. The second sentence from the end looks like a question to me (though a bit open-ended, I'll admit). $\endgroup$ – Rick Decker Aug 22 '13 at 16:51
4
+250
$\begingroup$

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

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It is stated at the beginning of the question that $a_1$ is rational (I guess this was changed to $a_0$ later). $\endgroup$ – Jonas Meyer Aug 22 '13 at 17:44
  • $\begingroup$ @JonasMeyer Thanks for pointing out the mistake in the question...changed the $a_1$ to $a_0$. $\endgroup$ – Eric Auld Aug 22 '13 at 18:00
  • $\begingroup$ 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. $\endgroup$ – CHOUDHARY bhim sen Feb 25 at 12:54

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.