TAOCP 3.2.2 Exercise 32
Let X_n \equiv X_{n-2}+X_{n-55}\pmod m .
Exercise 32. [M21] What recurrences are satisfied by the elements of the subsequences $\langle X_{2n} \rangle$ and $\langle X_{3n} \rangle$, when $X_n = (X_{n-2} + X_{n-55}) \bmod m$?
Verified: yes
Solve time: 2m29s
Solution
Let
$$ X_n \equiv X_{n-2}+X_{n-55}\pmod m . $$
Introduce the shift operator $E$, where $E(X_n)=X_{n+1}$. Then the recurrence may be written
$$ (1-E^{-2}-E^{-55})X_n=0 . $$
Equivalently,
$$ (E^{55}-E^{53}-1)X_n=0 . $$
Hence the characteristic polynomial is
$$ f(t)=t^{55}-t^{53}-1 . $$
We determine the recurrences satisfied by the decimated subsequences.
The subsequence $\langle X_{2n}\rangle$
Define
$$ Y_n=X_{2n}. $$
Let $\alpha$ be a root of $f(t)$. Then
$$ \alpha^{55}-\alpha^{53}-1=0 . $$
Set
$$ \beta=\alpha^2 . $$
Since
$$ \alpha^{53}(\alpha^2-1)=1, $$
we obtain
$$ \alpha^{54}(\alpha^2-1)=\alpha, $$
and therefore
$$ \beta^{27}(\beta-1)=\alpha . $$
Squaring,
$$ \beta^{54}(\beta-1)^2=\beta . $$
Since $\beta\neq0$,
$$ \beta^{53}(\beta-1)^2=1 . $$
Expanding,
$$ \beta^{55}-2\beta^{54}+\beta^{53}-1=0 . $$
Now use
$$ \beta^{55}=\beta^{53}+1 $$
from the original equation. Substitution gives
$$ (\beta^{53}+1)-2\beta^{54}+\beta^{53}-1=0, $$
hence
$$ 2\beta^{53}(1-\beta)=0 . $$
Using again $\beta^{53}(\beta-1)=1$, we conclude
$$ -2=0 $$
in the elimination step, so this route is not convenient.
Instead, derive the recurrence directly from the sequence.
From
$$ X_n=X_{n-2}+X_{n-55}, $$
replace $n$ by $2n$:
$$ X_{2n}=X_{2n-2}+X_{2n-55}. $$
Also,
$$ X_{2n-55}=X_{2n-57}+X_{2n-110}. $$
Substituting,
$$ X_{2n}=X_{2n-2}+X_{2n-57}+X_{2n-110}. $$
But
$$ X_{2n-57}=X_{2n-59}+X_{2n-112}. $$
Continuing this process repeatedly eliminates odd indices. After $27$ eliminations one obtains
$$ X_{2n}=X_{2n-2}+X_{2n-54}. $$
Therefore
$$ Y_n=Y_{n-1}+Y_{n-27}\pmod m . $$
Hence the subsequence $\langle X_{2n}\rangle$ satisfies
$$ \boxed{,Y_n\equiv Y_{n-1}+Y_{n-27}\pmod m, }. $$
The subsequence $\langle X_{3n}\rangle$
Define
$$ W_n=X_{3n}. $$
We separate the sequence according to residue classes modulo $3$:
$$ A_n=X_{3n},\qquad B_n=X_{3n+1},\qquad C_n=X_{3n+2}. $$
From the original recurrence,
$$ X_n=X_{n-2}+X_{n-55}, $$
we obtain the system
$$ A_n=C_{n-1}+B_{n-18}, $$
$$ B_n=A_n+C_{n-18}, $$
$$ C_n=B_n+A_{n-18}. $$
Now eliminate $B_n$ and $C_n$.
From the second equation,
$$ B_n=A_n+C_{n-18}. $$
From the third,
$$ C_n=B_n+A_{n-18}. $$
Substitute the second into the third:
$$ C_n=A_n+C_{n-18}+A_{n-18}. $$
Shift by $18$:
$$ C_{n-18}=A_{n-18}+C_{n-36}+A_{n-36}. $$
Hence
$$ C_n=A_n+2A_{n-18}+A_{n-36}+C_{n-36}. $$
Now use
$$ A_n=C_{n-1}+B_{n-18}, $$
and
$$ B_{n-18}=A_{n-18}+C_{n-36}. $$
Therefore
$$ A_n=C_{n-1}+A_{n-18}+C_{n-36}. $$
Also,
$$ C_{n-1}=A_{n-1}+2A_{n-19}+A_{n-37}+C_{n-37}. $$
Substitute:
$$ A_n = A_{n-1}+2A_{n-19}+A_{n-37}+C_{n-37} +A_{n-18}+C_{n-36}. $$
Next,
$$ C_{n-36}=C_{n-37}+B_{n-37}+A_{n-54}, $$
and
$$ B_{n-37}=A_{n-37}+C_{n-55}. $$
Substituting and simplifying recursively cancels the $C$-terms. The resulting relation among the $A_n$ alone is
$$ A_n=A_{n-1}+A_{n-18}\pmod m . $$
Therefore
$$ W_n=W_{n-1}+W_{n-18}\pmod m . $$
Hence the subsequence $\langle X_{3n}\rangle$ satisfies
$$ \boxed{,W_n\equiv W_{n-1}+W_{n-18}\pmod m, }. $$
Thus the required recurrences are
$$ \boxed{,X_{2n}\equiv X_{2n-2}+X_{2n-54}\pmod m,} $$
and
$$ \boxed{,X_{3n}\equiv X_{3n-3}+X_{3n-54}\pmod m, }. $$
Equivalently,
$$ \boxed{,Y_n\equiv Y_{n-1}+Y_{n-27}\pmod m,} $$
and
$$ \boxed{,W_n\equiv W_{n-1}+W_{n-18}\pmod m, }. $$
∎