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

Consider the following sequence: let a0>0 be rational. Define an+1=an1{an}, where {an} is the fractional part of an (i.e. {an}=anan). Show that an converges, and find its limit.

We can show it converges as follows: suppose an=pn/qn=kn+rn/qn, where pn=knqn+rn, 0rn<qn. Then an+1=pn/qn1rn/qn=pnqnrn,so the denominator will keep decreasing until it is a divisor of p0 (maybe 1). Also, note we may take pn=p0 for all n.

Further, the limit will be p0gcf(p0,q0), because if fp0 and fqn, then f(p0knqn)=rn, so fqnrn=qn+1. But the limit may be strictly smaller; for instance, a0=30/7 converges right away to 6.

Can we say anything else about the limit of a sequence starting with a0? 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=a1q+r1
  • p=a2(qr1)+r2
  • p=a3(qr1r2)+r3
  • etc.

and try to solve for the remainders in the form ri=cipdiq, there is a nice recursive relation:

First, c1=1 and d1=a1, and in general,

cj=1+aj(c1++cj1) and

We can also write cj(1+aj)=c1++cj so that
cj=1+ajaj1(cj1(1+aj1)1). This can be expanded further to obtain the form

cj=1+aj[1+(1+aj1)[1+(1+aj2)[1+[1+(1+a2)]]], or even


Note that the ai are strictly increasing in the sequence. Suppose the procedure terminates at the n-th step (when rn=0). The limit is then p/an, and 0=rn=cn(p/q)dn or that p/q=dn/cn.

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=r1=c1(p/q)d1=p/qa1, so that q is a divisor of p, and the limit is p/q.

For termination at the second step, 0=r2=c2(p/q)d2=(1+a2)(p/q)(1+a1)a2, or that pq=(1+a1)a21+a2. If there exists a1<a2 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/d1<d, then the sequence terminates in the second step to p/d=(1+a1).

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

Third step termination: pq=(1+a1)(1+a2)a31+a3(1+(1+a2)), limit is (1+a1)(1+a2), and etc.

Also, it appears that if you plug in an=d in any formula, you can generate for which p the process converges to d by substituting any a1<a2<<an1<d. Maybe there's more special structure...

Source : Link , Question Author : Eric Auld , Answer Author : Evan

Leave a Comment