# Prove that this recurrence always cycles

If $n$ is a nonnegative integer, let $S_n=\{0, 1, 2, \dots, 2n+1\}$. For $t\in S_n$ repeatedly perform

 if t is even
t = t/2
else
t = (n + 1 + ⌊t/2⌋)


It seems that ultimately $t$ becomes equal to the initially chosen number.

For instance, if $n = 15$ (so $S_{15} = \{0, 1, 2, \dots, 31\}$):

For $t=1$;
$1 - 16- 8- 4- 2 - 1$

For $t=3$;
$3 - 17 - 24 - 12 - 6 - 3$

Prove that this property is always true for any $n$ and $t$ where $n\geq 0$ and $0\leq t\leq (2n+1)$. Also, For a given value of $T$, how can I find a number in $S_n$ which will be never be encountered while following this property for $T$?

-
What have you tried? If this is homework, tag it as such. –  lhf Jul 9 '12 at 11:57
No, its not a Homework. –  abhinav8 Jul 9 '12 at 12:03

You already have two good answers to your first question, that your operation $$t\rightarrow \begin{cases} t/2 & \text{if t is even}\\ n+1+\lfloor t/2\rfloor & \text{if t is odd} \end{cases}$$ will generate a sequence that will eventually return to whatever starting value you use. For your second question, Jyrki has noted that this is closely related to the prefect shuffle operation. For example, with $n=7$, starting with $t=3$ your transformation would yield the sequence $$3\rightarrow 9\rightarrow 12\rightarrow 6\rightarrow 3$$ Consider the set $S_7=\{0, 1, \dots, 15\}$ as a deck of 16 cards, initially ordered. A perfect out-shuffle, as it's known, takes that deck, splits it into two equal-sized piles, $\langle\; 0, 1, 2, 3, 4, 5, 6, 7\;\rangle$ and $\langle\; 8, 9, 10, 11, 12, 13, 14, 15\;\rangle$, and then reassembles them in a new order by alternately interleaving the two piles, giving you $$\begin{array}{cccccccccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ 0 & 8 & 1 & 9 & 2 & 10 & 3 & 11 & 4 & 12 & 5 & 13 & 6 & 14 & 7 & 15 \end{array}$$ where the second row is the card values and the top row is their positions in the new deck order. We can view this permutation as indicating that the card in position 3 will be placed in position 9, the card in position 9 will go in position 12, the card in position 12 will be placed in position 6 and the card in position 6 will be placed in position 3, where we started. Doing this for all cards gives a disjoint cycle decomposition, $$(0)(1\ 8\ 4\ 2)(3\ 9\ 12\ 6)(5\ 10)(7\ 11\ 13\ 14)(15)$$ It's no coincidence (and it's fairly easy to show) that the $(3\ 9\ 12\ 6)$ cycle is exactly the same as your transformation produced and that this holds in general.

This, then, is a long-winded way of answering your second question: given any $T$, repeated iteration of your transformation will miss all the values not in the cycle containing $T$. In particular, for any $n$, the cycle starting with $0$ will miss value $2n+1$, the cycle starting with $2n+1$ will miss $0$ and any other starting value will miss both $0$ and $2n+1$ (which, I'll admit, doesn't actually need any of the results I've shown, but it's too pretty not to mention).

-

Hint : Each operation has an inverse, i.e., given a number t, there exists a unique successor and for every number, there's a unique predecessor. Once you prove this, the rest follows. Note that the even numbers map to the first half and odds map to the second half.

-

You're iterating a function $f: X \to X$ where $X=\{ 0, 1, \dots, 2n+1 \}$ and considering the orbit a point $t\in X$ under $f$. Since $X$ is a finite set, the iteration must repeat some number in $X$. Once it repeats that number, it cycles forever. Thus the orbit ends with a cycle. Now, since $f$ is injective, the orbit must be the whole cycle and so it comes back to the initial $t$.

-
The cycle structure of $f$ is actually pretty interesting, though I don't know the general pattern. For some $n$, all orbits have the same length except for the obvious two orbits of length 1. For other $n$, it's more more distributed. –  lhf Jul 9 '12 at 12:50
The operation seems to be essentially the inverse of a (variant of) perfect shuffle on a deck of an even number of cards. As the inverse shares the cycle structure, a lot is known... –  Jyrki Lahtonen Jul 9 '12 at 14:50
@JyrkiLahtonen, thanks! The Wikipedia page on the perfect shuffle has a reference to the cycle structure at the bottom of the page. –  lhf Jul 9 '12 at 16:07