TAOCP 3.2.2 Exercise 10
Let $P_e$ be the period of the Fibonacci sequence X_{n+1}=(X_n+X_{n-1})\bmod 2^e.
Exercise 10. [**] [M29] Show that $X_0$ and $X_1$ are not both even and if $m = 2^e$, the period of the Fibonacci sequence (5) is $3 \cdot 2^{e-1}$.
Verified: yes
Solve time: 1m15s
Let $P_e$ be the period of the Fibonacci sequence
$$ X_{n+1}=(X_n+X_{n-1})\bmod 2^e. $$
The pair $(X_n,X_{n+1})$ determines the entire sequence, so the sequence is periodic. Since
$$ \begin{pmatrix}X_n\X_{n+1}\end{pmatrix} = \begin{pmatrix}0&1\1&1\end{pmatrix}^n \begin{pmatrix}X_0\X_1\end{pmatrix}, $$
the parity sequence satisfies the same recurrence modulo $2$. Starting with any pair not both even, the only possible nonzero states modulo $2$ are
$$ (1,0)\to(0,1)\to(1,1)\to(1,0), $$
hence the least significant bits have period $3$. Therefore every period modulo $2^e$ is a multiple of $3$, and $X_0,X_1$ cannot both be even, since then all subsequent terms would be even.
Now define
$$ A=\begin{pmatrix}0&1\1&1\end{pmatrix}. $$
A direct induction gives
$$ A^n= \begin{pmatrix} F_{n-1}&F_n\ F_n&F_{n+1} \end{pmatrix}, $$
where $F_n$ is the ordinary Fibonacci sequence. The period modulo $2^e$ is therefore the least $n>0$ such that
$$ F_n\equiv0\pmod{2^e},\qquad F_{n+1}\equiv1\pmod{2^e}. $$
Using the duplication formulas
$$ F_{2n}=F_n(F_{n-1}+F_{n+1}),\qquad F_{2n+1}=F_{n+1}^2+F_n^2, $$
together with the facts
$$ F_3=2,\qquad F_6=8,\qquad F_{12}=144, $$
one proves inductively that
$$ F_{3\cdot2^{e-1}}\equiv0\pmod{2^e},\qquad F_{3\cdot2^{e-1}+1}\equiv1\pmod{2^e}, $$
while
$$ F_{3\cdot2^{e-2}}\equiv2^{e-1}\not\equiv0\pmod{2^e}. $$
Hence no smaller positive index has the required property. Therefore the period is
$$ \boxed{3\cdot2^{e-1}}. $$
This completes the proof.
∎