Числа без 00 в двоичной

[kthxbye]

Пусть $a(n)$ - это последовательность чисел, таких, что в двоичном представлении они как начинаются, так и заканчиваются единицей и не содержат ни одной пары нулей идущих подряд (соот.-но ни одной тройки, четверки и т.д.).

Последовательность начинается так:

$$1, 3, 5, 7, 11, 13, 15, 21, 23, 27, 29, 31, 43, 45, 47, 53, 55, 59, 61, 63$$

Пусть $b(n)$ - это последовательность чисел, таких, что в двоичном представлении число нулей в крайней справа последовательности нулей равно числу всех остальных нулей.

Последовательность начинается так:

$$1, 3, 7, 10, 15, 22, 26, 31, 36, 46, 54, 58, 63, 76, 84, 94, 100, 110, 118, 122, 127$$

Докажите, что осуществляя трансформацию $1\to1$, $01\to0$ над $a(n)$, а также приписывая справа единицу и вместе с ней нули в том же количестве, в каком они содержатся в $a(n)$ мы получаем $b(n+1)$.

[waxtep]

Кажется, достаточно так рассудить:
1. Какой-нибудь представитель последовательности $a$ содержащий $d$ двоичных разрядов обязательно трансформируется в представителя $b$ из $d+1$ разряда;
2. Трансформация взаимно-однозначна и для каждого представителя $b$ есть прообраз в $a$;
3. Трансформация сохраняет порядок (в записи числа единичка "старше" нуля в $b$, и точно также (неимеющая слева нуля) $1$ "старше" $01$ в $a$;
4. $a(1)$ действительно трансформируется в $b(2)$, а дальше уж им и деваться некуда в силу пп. 1-3. Для каждой разрядности $d$ представителей $a$ столько же, сколько представителей $b$ разрядности $d+1$ и следуют они в одном и том же и порядке.