
Problem 9.3. Let $A_{n}$ be the number of sequences from 0 's and 1 's of length $n$, such that no four consequtive elements equal 0101. Find the parity of $A_{2001}$.


Solution: Denote the number of sequences of length $n$, the last three terms of which are $i j k$, where $i, j, k \in\{0,1\}$ and no four consequtive elements equal to 0101 by $a_{i j k}^{n}$.

Obviously $a_{i j k}^{n+1}=a_{0 i j}^{n}+a_{1 i j}^{n}$ when $i j k \neq 101$ and $a_{101}^{n+1}=a_{110}^{n}$. Adding the above equalities for all values of $i j k$ we obtain $A_{n+1}=2 A_{n}-a_{010}^{n}$.

Therefore $A_{n+1} \equiv a_{010}^{n} \equiv a_{001}^{n-1}+a_{101}^{n-1} \equiv a_{000}^{n-2}+a_{100}^{n-2}+a_{110}^{n-2} \equiv$ $a_{000}^{n-3}+a_{100}^{n-3} \equiv a_{000}^{n-4}+a_{100}^{n-4}+a_{010}^{n-4}+a_{110}^{n-4} \equiv a_{000}^{n-5}+a_{001}^{n-5}+a_{010}^{n-5}+$ $a_{100}^{n-5}+a_{111}^{n-5}+a_{110}^{n-5}+a_{101}^{n-5}+a_{011}^{n-5}+\equiv A_{n-5}(\bmod 2)$.

Thus, $A_{k+6 m} \equiv A_{k}(\bmod 2)$ for all $k$ and $m$.

Therefore $A_{2001} \equiv A_{3}=8 \equiv 0(\bmod 2)$.
