Маленькая лемма

[kthxbye]

В одном доказательстве (относительно вот этого вопроса) требуется уточнить одну маленькую и вероятно очень простую лемму.

Пусть $\operatorname{wt}(n)$ это A000120, число единиц в двоичном разложении $n$ (или просто бинарный вес $n$). Здесь

$$\operatorname{wt}(n)=\operatorname{wt}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n\bmod2, \operatorname{wt}(0)=0$$

Пусть $T(n,k)$ это A295989, $(k+1)$-ое неотрицательное число $m$, такое, что $n\operatorname{AND}m=m$. Другое определение - числа в порядке возрастания, получаемые в результате замены (всеми возможными способами) единиц на нули в двоичном разложении $n$. Еще одно определение - числа $m$, такие, что $\binom{n}{m}\bmod2=1$. Здесь

$$T(2n,k)=2T(n,k), T(2n+1,k)=2T\left(n,\left\lfloor\frac{k}{2}\right\rfloor\right)+k\bmod2, T(n,0)=0$$

Требуется доказать, что

$$\operatorname{wt}(T(n,k))=\operatorname{wt}(k)$$

Я пробовал использовать разложение

$$n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_{wt(n)}+1}))\dots)$$

но оно дает лишь

$$\sum\limits_{j=0}^{\operatorname{wt}(k)}\left\lfloor\frac{k}{2^j}\right\rfloor\bmod2$$

а надо чтобы было

$$\sum\limits_{j=0}^{\left\lfloor\log_{2}{k}\right\rfloor}\left\lfloor\frac{k}{2^j}\right\rfloor\bmod2$$

[svv]

Запишем двоичное разложение $n$, обозначая нули кружочком $\bullet$, а единицы вопросительным знаком $?$ (считаем, что эти символы — альтернативные обозначения для нуля и единицы).
Тогда двоичное разложение любого $T(n,k)$ получится заменой каждого вопросительного знака либо на $0$, либо на $1$. А если из этого разложения убрать все кружочки $\bullet$, получится разложение $k$. Поэтому в разложениях $T(n,k)$ и $k$ одно и то же число единиц.

Например, $n=26$ запишем как $??\bullet ?\bullet$ и перечислим все $T(n,k)$ и соответствующие $k$:
$\begin{tabular}{c|c}$T(n,k)$ & $k$ \\\hline$00\!\bullet\! 0\bullet $ & $000$ \\$00\!\bullet\! 1\bullet $ & $001$ \\$01\!\bullet\! 0\bullet $ & $010$ \\$01\!\bullet\! 1\bullet $ & $011$ \\$10\!\bullet\! 0\bullet $ & $100$ \\$10\!\bullet\! 1\bullet $ & $101$ \\$11\!\bullet\! 0\bullet $ & $110$ \\$11\!\bullet\! 1\bullet $ & $111$ \end{tabular}$
​

[kthxbye]

svv, гениально! Благодарю за ответ.