Общая формула
![$a_n = (1- n \mod 2) - a_{[n/2]}$ $a_n = (1- n \mod 2) - a_{[n/2]}$](https://dxdy-04.korotkov.co.uk/f/3/8/f/38fb07c91ec908b4d250c2ec093ff53382.png)
Отсюда
![$a_n = (1- n \mod 2) - (1- \left[ \frac{n}{2^1}\right] \mod 2) + ... + (1- \left[ \frac{n}{2^{2N-1}}\right] \mod 2) - (1- \left[ \frac{n}{2^{2N}}\right] \mod 2)$ $a_n = (1- n \mod 2) - (1- \left[ \frac{n}{2^1}\right] \mod 2) + ... + (1- \left[ \frac{n}{2^{2N-1}}\right] \mod 2) - (1- \left[ \frac{n}{2^{2N}}\right] \mod 2)$](https://dxdy-03.korotkov.co.uk/f/a/2/e/a2eb760fceccfb2da80ccaa495c31c9282.png)
![$a_n = - n \mod 2 + \left[ \frac{n}{2^1}\right] \mod 2 - ... - \left[ \frac{n}{2^{2N-1}}\right] \mod 2 + \left[ \frac{n}{2^{2N}}\right] \mod 2$ $a_n = - n \mod 2 + \left[ \frac{n}{2^1}\right] \mod 2 - ... - \left[ \frac{n}{2^{2N-1}}\right] \mod 2 + \left[ \frac{n}{2^{2N}}\right] \mod 2$](https://dxdy-04.korotkov.co.uk/f/b/9/4/b945ecca010c16dcc61b8182f95ecc0382.png)
.

всегда. Предположим, что есть хотя бы еще одно

, то есть

. Тогда из формулы выше для

следует, что

. Тогда достаточно доказать

только для

, у которых только

, а остальные

Обозначим
![$s_1 = \sum\limits_{j \geq 0} \left[ \frac{3n}{4^j}\right] \mod 2$ $s_1 = \sum\limits_{j \geq 0} \left[ \frac{3n}{4^j}\right] \mod 2$](https://dxdy-03.korotkov.co.uk/f/e/8/d/e8d173967b8de2d1c5e4db2b16e2f9c782.png)
,
![$s_2 = \sum\limits_{j \geq 0} \left[ \frac{3n}{2 \cdot 4^j}\right] \mod 2$ $s_2 = \sum\limits_{j \geq 0} \left[ \frac{3n}{2 \cdot 4^j}\right] \mod 2$](https://dxdy-03.korotkov.co.uk/f/a/9/1/a91d67dca97b5d9c7f3ad51d3292e3c782.png)
и докажем, что


![$\left[\frac{3n}{4^k}\right]=\sum\limits_{j \geq k}d_j4^{j-k} + [\epsilon _{k-1}]$ $\left[\frac{3n}{4^k}\right]=\sum\limits_{j \geq k}d_j4^{j-k} + [\epsilon _{k-1}]$](https://dxdy-02.korotkov.co.uk/f/9/5/9/959915a76167fb143d5d6c5cb41c79b282.png)
![$\left[\frac{3n}{2\cdot 4^k}\right]=\sum\limits_{j \geq k+1}2d_j4^{j-k-1} + [\epsilon _k]$ $\left[\frac{3n}{2\cdot 4^k}\right]=\sum\limits_{j \geq k+1}2d_j4^{j-k-1} + [\epsilon _k]$](https://dxdy-02.korotkov.co.uk/f/5/7/9/57945366135ed39fe27662a8618a4eb482.png)
,
где

.
И тогда
![$s_1 = \sum\limits_j (d_j +[\epsilon _{j-1}]) \mod 2$ $s_1 = \sum\limits_j (d_j +[\epsilon _{j-1}]) \mod 2$](https://dxdy-02.korotkov.co.uk/f/9/c/2/9c2fde6e89259a15b189a3019fd1e76182.png)
,
![$s_2 = \sum\limits_j [\epsilon _j] \mod 2$ $s_2 = \sum\limits_j [\epsilon _j] \mod 2$](https://dxdy-01.korotkov.co.uk/f/8/9/a/89abeb8ce95aef42c7b6ff49446b4cba82.png)
. Вычислим обе суммы, сначала

, потом

.
Последовательность "цифр"

имеет вид:

. Каждая "горка"

переводится оператором

в

, поэтому в сумме

для "цифр"

будет всегда

(каждому слагаемому

соответствует "цифра"

), поэтому

равно числу нулей в последовательности "цифр"

+ константа. Константа эта равна 1 - ее находим из рассмотрения начала последовательности

, начинающейся на 1 (номер

). Для

каждое слагаемое равно
![$(d_j +[\epsilon _{j-1}]) \mod 2$ $(d_j +[\epsilon _{j-1}]) \mod 2$](https://dxdy-02.korotkov.co.uk/f/9/e/5/9e5f498ea379f3ce75ec761894673a4a82.png)
, "цифра"

принимает 2 раза значение 1 на краях "горки", а

для всех нулей "горки" и для ее левого края (ему соответствует число 1), так что "горка" из

нулей дает вклад из

единиц в сумму. Значит

тоже равна числу нулей в последовательности + постоянная, а постоянная равна 1, что находим из рассмотрения слагаемого с номером

.
Таким образом, обе суммы равны 1 + число нулей в последовательности "цифр"

числа

, а значит равны.
Что-то для меня это не совсем детсадовское. Может быть есть решение проще?
