## Sequences related to maps based on simple fractional functions

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, 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, f=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, f=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, f=1, f=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). 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. 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. 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. 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$

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