Suppose one has in hand an infinite sequence $s$ of distinct natural numbers, for example,

$$s=s_1=(1, 3, 5, 7, 9, 11, 13, 15, 17, 19,\ldots) \;.$$

So this sequence can be considered an injection $f: \mathbb{N} \mapsto \mathbb{N}$.

Now replace $s_1$ with $s_2$ by indexing in $s_1$ using $s_1$:
$$s_2=(1, 5, 9, 13, 17, 21, 25, 29, 33, 37,\ldots) \;.$$
So we take the 1st, 3rd, 5th, ... elements of $s_1$ to form $s_2$.
To construct $s_3$, index into $s_2$ using $s_2$:
take the 1st, 5th, 9th, ... elements of $s_2$, i.e.,
$$s_3=(1, 17, 33, 49, 65, 81, 97, 113, 129, 145,\ldots) \;.$$
Note that, e.g., the 2nd element of $s_3$ is *not* $f^3(2) = 9$,
but rather $f^2( f^2( 2)) = f^4(2) = 17$.
Iterating once more we reach
$$s_4=(1, 257, 513, 769, 1025, 1281, 1537, 1793, 2049, 2305,\ldots)\;. $$
Here, e.g., the 2nd element of $s_4$ is $f^8(2)=256 \cdot 2 - 255 = 257$.

Several questions:

**Q1**.
For which starting sequences $s$ does this process lead to a fixed
sequence, $s_k = s_{k+1}$? Certainly it does if $s$ represents
the identity: $s_1=(1,2,3,4,5,\ldots)$. Are there any other
fixed sequences?

**Q2**.
For which starting sequences $s$ does this process lead to a cycle
among the sequences, $s_k = s_{k+m}$, $m>1$? And can the length of such a cycle be predicted from
the structure of the starting sequence?

**Q3**. What is the expected behavior under iteration of a "typical" (random?) starting injection $s$,
under any reasonable sense of "typical"?

I feel certain this has all been studied before, and I am just not phrasing it in an easily recognizable manner. I would appreciate pointers—Thanks!

whyfor each, some indication of your reasoning? Thanks! $\endgroup$ – Joseph O'Rourke Oct 29 '11 at 1:08