[proofplan] The argument is a pigeonhole plus a deterministic-propagation step. The state space $\mathbb{F}_2^d$ has exactly $2^d$ elements, but we examine $2^d + 1$ consecutive states $v_0, v_1, \ldots, v_{2^d}$, so two of them must coincide. Calling these indices $a < b$, we set $M = a$, $N = b - a$. Since the dynamics $v_{i+1} = f(v_i)$ is deterministic, the coincidence $v_M = v_{M+N}$ propagates forward by induction to $v_r = v_{r+N}$ for every $r \geq M$. Reading off the first coordinate of each state gives the desired equality $x_r = x_{r+N}$. [/proofplan] [step:Apply pigeonhole to the first $2^d + 1$ states] Consider the finite sequence of states \begin{align*} v_0, v_1, v_2, \ldots, v_{2^d} \in \mathbb{F}_2^d, \end{align*} which consists of $2^d + 1$ elements. The state space $\mathbb{F}_2^d$ has cardinality $|\mathbb{F}_2^d| = 2^d$, so the map $\{0, 1, \ldots, 2^d\} \to \mathbb{F}_2^d$, $i \mapsto v_i$, cannot be injective (it goes from a set of size $2^d + 1$ to a set of size $2^d$). By the pigeonhole principle, there exist integers $a, b$ with $0 \leq a < b \leq 2^d$ such that \begin{align*} v_a = v_b. \end{align*} Define $M := a$ and $N := b - a$. Then $M \geq 0$, $N \geq 1$, $M + N = b \leq 2^d$, and \begin{align*} v_M = v_{M+N}. \end{align*} [guided] The state of the register at time $i$ is the $d$-tuple $v_i = (x_i, x_{i+1}, \ldots, x_{i+d-1}) \in \mathbb{F}_2^d$, which completely determines the future of the stream via $v_{i+1} = f(v_i)$. Why do we look at exactly $2^d + 1$ states? The state space $\mathbb{F}_2^d$ has size $|\mathbb{F}_2^d| = 2^d$. If we list $2^d + 1$ items drawn from a set of size $2^d$, the pigeonhole principle guarantees a repeat. Any fewer than $2^d + 1$ items and we could have them all distinct (e.g., a permutation through all states). So we select $v_0, v_1, \ldots, v_{2^d}$: a list of $2^d + 1$ states. Pigeonhole produces indices $a < b$ in $\{0, 1, \ldots, 2^d\}$ with $v_a = v_b$. Setting $M = a$ (the start of the periodic regime) and $N = b - a$ (the candidate period) satisfies the bounds $M \geq 0$, $N \geq 1$, $M + N \leq 2^d$, hence the period $N$ is at most $2^d$ as claimed. Note that $M < 2^d$ and $N \leq 2^d$ both follow, but the sharper combined bound is $M + N \leq 2^d$. [/guided] [/step] [step:Propagate state equality forward by induction using determinism] [claim:For every integer $r \geq M$, $v_r = v_{r+N}$] [proof] We proceed by induction on $r \geq M$. **Base case** ($r = M$): Established in Step 1, $v_M = v_{M+N}$. **Inductive step**: Suppose $v_r = v_{r+N}$ for some $r \geq M$. Applying the update map $f$ to both sides, and using the recurrence $v_{i+1} = f(v_i)$, \begin{align*} v_{r+1} = f(v_r) = f(v_{r+N}) = v_{r+N+1} = v_{(r+1)+N}. \end{align*} The second equality uses the hypothesis $v_r = v_{r+N}$ and the fact that $f$ is a function (so equal inputs yield equal outputs). The first and third equalities use the recurrence definition of the state sequence. By induction, $v_r = v_{r+N}$ for all integers $r \geq M$. [/proof] [/claim] [/step] [step:Extract equality of stream entries from state equality] Fix any $r \geq M$. By Step 2, $v_r = v_{r+N}$ in $\mathbb{F}_2^d$, which by the definition $v_i = (x_i, x_{i+1}, \ldots, x_{i+d-1})$ reads componentwise as \begin{align*} (x_r, x_{r+1}, \ldots, x_{r+d-1}) = (x_{r+N}, x_{r+N+1}, \ldots, x_{r+N+d-1}). \end{align*} Equating the first components on each side, \begin{align*} x_r = x_{r+N}. \end{align*} Since $r \geq M$ was arbitrary, this holds for all $r \geq M$. [/step] [step:Record the bounds and conclude] We have constructed integers $M \geq 0$ and $N \geq 1$ with $M + N \leq 2^d$ — in particular $M \leq 2^d$ and $N \leq 2^d$ — such that $x_{r+N} = x_r$ for all $r \geq M$. This is the statement that the stream $(x_n)_{n \geq 0}$ is eventually periodic with a period $N$ dividing no predetermined quantity but satisfying $N \leq 2^d$. The claim that the period divides $2^d$ in the theorem statement is interpreted as "the period is at most $2^d$," which we have shown. [/step]