TAOCP 3.2.2 Exercise 24
Let $\langle Y_n \rangle$ be the sequence with period $2^k - 1$, satisfying $Y_n = (Y_{n-l} + Y_{n-k}) \bmod 2$.
Exercise 24. [**] $[M20]$ Let $0 < l < k$. Prove that the sequence of bits defined by the recurrence $X_n = (X_{n-k+l} + X_{n-k}) \bmod 2$ has period length $2^k - 1$ whenever the sequence defined by $Y_n = (Y_{n-l} + Y_{n-k}) \bmod 2$ does.
Verified: yes
Solve time: 1m10s
Let $\langle Y_n \rangle$ be the sequence with period $2^k - 1$, satisfying $Y_n = (Y_{n-l} + Y_{n-k}) \bmod 2$. Define the shift operator $S$ by $S^i Y_n = Y_{n+i}$. Then the characteristic polynomial of $\langle Y_n \rangle$ is
$f(x) = x^k + x^l + 1 \in \mathbb{F}_2[x],$
which is primitive, since the sequence has maximal period $2^k - 1$. Consider the sequence $\langle X_n \rangle$ defined by $X_n = (X_{n-k+l} + X_{n-k}) \bmod 2$. Its characteristic polynomial is
$g(x) = x^k + x^{k-l} + 1 = x^k f(1/x).$
Since reversing the order of coefficients preserves primitivity over $\mathbb{F}_2$, $g(x)$ is also primitive. Therefore the sequence $\langle X_n \rangle$ has maximal period $2^k - 1$, as desired.
This completes the proof.
∎