Битовая последовательность

[Dave]

Последовательность $\{B_n\}_{n=0}^{\infty}\,,$ состоящая из нулей и единиц, при $n<2^m$, где $m$ - фиксированное натуральное число, определена произвольно, а далее строится по рекуррентному соотношению

$$B_n=\bigoplus_{i=0}^m {B_{n-2^i}}\,,$$

т.е. любой её элемент $B_n$ при $n \geqslant 2^m$ равен сумме по модулю 2 элементов $B_{n-1}, B_{n-2}, B_{n-4}, \dots, B_{n-2^m}$. Докажите, что эта последовательность периодична с периодом $2^{m+1}-1$.

[TOTAL]

Обозначим $T^{k}B_n=B_{n-k}$ и запишем заданное в условии соотношение как

$$B_n=\left( \sum_{i=0}^m T^{2^i} \right)B_n.$$

Умножив обе части на

$$\sum_{i=0}^m T^{2^i-1},$$

получим (по модулю $2$)

$$\left( \sum_{i=0}^m T^{2^i-1} \right)B_n=T\left( \sum_{i=0}^m T^{2^i-1} \right)^2B_n=T\left( \sum_{i=0}^m T^{2 \cdot 2^i-2} \right)B_n,$$

откуда следует требуемое равенство

$$B_n=T^{2^{m+1}-1}B_n$$

[Dave]

Да, красиво. Я решал не через операторы, а через многочлены, но суть та же.