TAOCP 7.1.3 Exercise 122

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 122. [M22] [M22] Complete the proof of Lemma B.

Verified: yes
Solve time: 1m56s

Let $S$ be a finite set with $|S|=N$, and let $f:S\to S$. Lemma B concerns the behavior of the sequence

$$ x, f(x), f^{(2)}(x), \dots $$

under iteration of $f$, namely that it is eventually periodic.

We now complete the proof.

Start with an arbitrary $x_0 \in S$, and define

$$ x_k = f^{(k)}(x_0), \quad k \ge 0. $$

Since $S$ has only $N$ elements, the sequence $x_0, x_1, \dots, x_N$ contains $N+1$ terms drawn from a set of size $N$. By the pigeonhole principle, there exist indices $0 \le i < j \le N$ such that

$$ x_i = x_j. $$

Fix such a pair with minimal $j-i>0$. Now apply $f$ repeatedly to both sides. For every $t \ge 0$,

$$ f^{(t)}(x_i) = f^{(t)}(x_j), $$

so

$$ x_{i+t} = x_{j+t}. $$

Let $p = j-i$. Then for all $t \ge 0$,

$$ x_{i+t} = x_{i+t+p}. $$

This shows that once the sequence reaches $x_i$, it repeats with period $p$. The initial segment $x_0, x_1, \dots, x_{i-1}$ is transient, and the sequence from $x_i$ onward is periodic.

Thus every orbit of $f$ is eventually periodic, which completes the proof of Lemma B.