Sequences related to maps based on simple fractional functions

Posted on December 25, 2019 by mAnasa-taraMgiNI

One of the pleasures of an unstructured youth in the pre-computer era was what we called calculator games. As our father took his prized calculator with him to work we only got a little time with it in the evenings. However, we got our break when a relative gifted us a Japanese solar-powered calculator. The roots (pun intended) of this note lies in the games that followed: One of those was determining the consequences of simple functional iterations. We soon realized that these are intimately related to some familiar and not so familiar sequences. Some of them were mysterious and beyond our calculator efforts. We finally cracked them and obtained a more formal understanding of the convergences only when our mathematical knowledge improved and we were in possession of a computer in the late phase of our youth. Consider maps which are iterates of simple fractional functions of the form:

x_0=0; \; x_n=\dfrac{1}{1+k x_{n-1}}

If k=1, n \to \infty, \; x_n \to \dfrac{1}{\phi}, where \phi is the Golden Ratio

One can see that the iterates of this map are sequence of fractions: 0, 1, 1/2, 2/3, 3/5, 5/8, 8/13, 13/21, 21/34. One notices that its terms are derived from the famous mātrā-meru sequence.

If k=2, n \to \infty, \; x_n \to \dfrac{1}{2}

x_n=\dfrac{1}{1}, \dfrac{1}{3}, \dfrac{3}{5}, \dfrac{5}{11}, \dfrac{11}{21}, \dfrac{21}{43}, \dfrac{43}{85}, \dfrac{85}{171}...

This sequence of fractions can be derived from the famous Jacobsthal sequence: 2f[n]+(-1)^n; f[1]= 1: 1, 3, 5, 11, 21, 43, 85, 171…
Like the mātrā-meru, the Jacobsthal sequence appears in numerous seemingly unrelated places in mathematics.

If k=3, x_n \to \dfrac{\sqrt{13}-1}{6} \approx 0.43425854591

Here x_n= 0, \dfrac{1}{1}, \dfrac{1}{4}, \dfrac{4}{7}, \dfrac{7}{19}, \dfrac{19}{40}, \dfrac{40}{97}...

One observes that these fractions are related to the sequence f[n]=f[n-1]+3f[n-2]; f[1]=1, f[2]=1:
1, 1, 4, 7, 19, 40, 97…

If k=\dfrac{1}{2}, x_n \to \sqrt{3}-1 \approx 0.73205080756888

Here x_n= 0, \dfrac{1}{1}, \dfrac{2}{3}, \dfrac{3}{4}, \dfrac{8}{11}, \dfrac{11}{15}, \dfrac{30}{41}, \dfrac{41}{56}, \dfrac{112}{153}...

These fractions are related to the sequence f[n]=2f[n-1]; f[n+1]=f[n]+f[n-2]; f[n+2]=f[n+1]+f[n-1]; f[1]=1, f[2]=1:
1, 1, 2, 3, 4, 8, 11, 15, 30, 41, 56, 112, 153…

If k=\dfrac{1}{3}, x_n \to \dfrac{\sqrt{21}-3}{2} \approx 0.79128784747792;

Here x_n=0, \dfrac{1}{1}, \dfrac{3}{4}, \dfrac{4}{5}, \dfrac{15}{19}, \dfrac{19}{24}, \dfrac{72}{91}, \dfrac{91}{115}, \dfrac{345}{436}, \dfrac{436}{551}...

These are related to the sequence f[n]=f[n-1]+f[n-3]; f[n+1]=f[n]+f[n-2]; f[n+2]=3f[n+1]; f[1]=1, f[2]=1, f[3]=3:
1, 1, 3, 4, 5, 15, 19, 24, 72, 91, 115, 345, 436, 551…

Now, one can use the substitution x_n=y_n-\tfrac{1}{k} to convert our map into an equivalent but alternative map:

y_{n+1}=\dfrac{1}{k}\left( 1+\dfrac{1}{y_n} \right)

By writing y_n=\tfrac{w_n}{w_{n-1}} the above map becomes a linear difference equation:

w_{n+1}=\dfrac{1}{k}(w_n+w_{n-1})

Such a linear difference equation defines the quadratic equation: y^2-\tfrac{y}{k}-\tfrac{1}{k}=0 with roots:

y=\dfrac{1\pm \sqrt{4k+1}}{2k}

Thus, the map in the variable y_n will be attracted to the greater root \tfrac{1+ \sqrt{4k+1}}{2k} and repelled by the lesser root \tfrac{1- \sqrt{4k+1}}{2k} for any starting value of y_n, except when y_0=\tfrac{1- \sqrt{4k+1}}{2k}; interesting aspects of the convergence of this type of map was discussed earlier. Now, given that x_n=y_n-\tfrac{1}{k}, we get the attractor A of our original maps in x_n to be:

A= \dfrac{\sqrt{4k+1}-1}{2k}

Now if k < -\tfrac{1}{4} then A will be a complex number. Given that our original maps of the form x_n=\tfrac{1}{1+k x_{n-1}} are defined in real space \mathbb{R}, what will happen to the iterates in such a case? Consider an example of k=-1 and x_0=-1. Here the map does not converge to a single attractor A but cycles between 3 values: -1, 1/2, 2. Now, if we use a different x_0=0 we get 0, 1, \infty. Thus, the 3 values that the iterates cycle through depends on x_0 but the cycle length is always 3.

Consider another case where k=-\tfrac{1}{3} and x_0=0. Here again the map does not converge to a single value but cycles through 6 different values: 0, 1, 3/2, 2, 3, \infty. Again the cycle length is always 6 though the actual values change with x_0. This cycling in the above examples immediately suggests a connection between the arithmetic operation of our map and trigonometry. This connection becomes clear from the form A takes:

If k<-\dfrac{1}{4}, \; A= -\dfrac{1}{2k}+i\dfrac{\sqrt{-4k-1}}{2k}

If we have a complex number z=x+iy then it defines an angle \theta=\textrm{Arg}(z)=\arctan\left(\tfrac{y}{x}\right) in the complex plane. Thus we get the angle corresponding to A to be:

\theta = \textrm{Arg}(A)= \arctan\left(-\sqrt{-4k-1}\right)

Since for our purposes the sign of the angle does not matter we can work with \theta= \arctan\left(\sqrt{-4k-1}\right). As an aside, we can also express this angle as \theta= \arccos\left(\tfrac{1}{2\sqrt{-k}}\right).

Now when A is real, \theta = \textrm{Arg}(A)=\pi. Thus, \tfrac{\pi}{\theta}=1 and our map converges to a single value, i.e. it has cycle length 1.

Instead, when say k=-1, \; \theta= \arctan\left(\sqrt{3}\right)=\tfrac{\pi}{3}. Thus, \tfrac{\pi}{\theta}=3 and our map has cycle length 3. Similarly, when k=-\tfrac{1}{3}, \; \theta = \tfrac{\pi}{6}. Thus, \tfrac{\pi}{\theta}=6 and our map has a cycle length 6.

What if k does not generate a \theta which is a rational sector of a circle? The simplest such example that is easily apprehended is k=-2. In such a case the map would never converge to single value or a cycle. However, we observe remarkable behavior where it oscillates through several overlapping cycles which are defined by “explosive'', much greater than average values (Figure 1-4).

frac_iterate_01

Figure 1 illustrates the cycle of length 13 (marked by red dots). One of these starts at n=13 and decays in terms of absolute magnitude at every 13th iterate thereafter: 26, 39, 52… Another starts at n=5 and increases in absolute value every 13th iterate thereafter: 18, 31, 44, 57… If one observes closely one see that there are smaller barely discernible cycles of 5, 3 and 2 nested within those of length 13.

frac_iterate_02

Figure 2 shows the next cycle of length 213 again increasing or decreasing in absolute magnitude at every 213th iterate (marked by red dots). Within each cycle of length 213 one can discern 16 cycles length 13.

frac_iterate_03

Figure 3 shows the next set of cycles of length 1291 (orange) and 1504 (red). One can discern 6 cycles of length 213 in each of the 1291 length cycles. There is a single cycle of length 1291 in that of length 1504.

frac_iterate_04

Figure 4 shows even larger cycles of length 4299 (green) and 10102 (red). The former includes 2 cycles of length 1504 within it. Likewise, the cycle of length 10102 includes 2 cycles of length 4299.

How do we derive these cycles lengths with no clear cut pattern from first principles? For the map defined by k=-2, the characteristic angle \theta=\arctan\left(\sqrt{7}\right). Thus, the cycles correspond to the numerators of the successive rational approximation fractions from the continued fraction representation of \tfrac{\pi}{\arctan\left(\sqrt{7}\right)}. Thus, we get the sequence of the cycle lengths to be:
2, 3, 5, 13, 213, 1291, 1504, 4299, 10102, 135625, 145727, 28135, 989783…

More generally, when \theta is not a rational sector of a circle the map shows cycles of increasing length that are specified by the numerators of the successive rational approximations obtained from the continued fraction for \tfrac{\pi}{\theta}.

We also notice the following curious pattern typical of rational fraction approximations for the successive cycle lengths:
\begin{aligned} 5 & = & 1 & \; \times & 3 & \; + & 2\\ 13 & = & 2 & \; \times & 5 & \; + & 3\\ 213 & = & 16 & \; \times & 13 & \; + & 5\\ 1291 & = & 6 & \; \times & 213 & \; + & 13\\ 1504 & = & 1 & \; \times & 1291 & \; +& 213\\ 4299 & = & 2 & \; \times & 1504 & \; + & 1291\\ 10102 & = & 2 & \; \times & 4299 & \; + & 1504\\ 135625 & = & 13 & \; \times & 10102 & \; + & 4299 \end{aligned}

Let C_n be the length of the cycle n. Thus,

C_n=kC_{n-1}+C_{n-2}

Hence, k will give the number of repeats of the previous cycle C_{n-1} which are contained in C_n.

Finally, let us consider the intertwined maps of the form where we alternate through \pm k:

x_n=\dfrac{1}{1+ky_{n-1}}; \; y_n=\dfrac{1}{1-kx_{n-1}}

This alternation forces a convergence to a point (C_x, C_y). Doing the algebra we can obtain,

C_x=\dfrac{2k+1-\sqrt{4k^2+1)}}{2k} \\[10pt] C_y=\dfrac{2k-1+\sqrt{4k^2+1)}}{2k}\\[10pt] C_x+C_y=2

Thus, as examples we have:
k=1; n \to \infty, \; x_n \to 2-\phi; \; y_n \to \phi, where \phi is the Golden Ratio.

k=2; n \to \infty, \; x_n\to \dfrac{5-\sqrt{17}}{4} \approx 0.21922359359558;\; y_n \to \dfrac{3+\sqrt{17}}{4} \approx 1.78077640640442

See also:
Golden cobwebs
Some Nārāyaṇa-like convergents and their geometric and trigonometric connections

This entry was posted in Scientific ramblings and tagged , , , , , , , , , . Bookmark the permalink.