Is this model of converting integers to Gray code correct?

Question

The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim.

Here is some information on how to use it.

Conversion model of all integers that have k digits in the binary system in Gray code.

Rules

1. You will need k columns of numbers. The numbers to be encoded are arranged in the last column.

2. The conversion is done gradually by transferring groups of numbers to the adjacent columns in the way the arrows show. There are two types of paired arrows, parallel (=) and intersecting (×). Symbolically, the (=) and (×) are considered inverse of each other.

3. Each column with arrows is formed by an exact copy of the previous column and by a copy of the previous column that has inverted pairs of arrows, which is placed below the exact copy.

Observation

If we set "=" = 0 and "×" = 1, then the successive columns containing arrows form the Thue Morse sequence which essentially forms the rules for converting integers to Gray code.

Answer 1

Yes, the proposed scheme always produces a Gray code. This can be proved by induction on $k$ as follows.

Proof. The base cases of $k=1,2$ are trivial. Assume that a Gray code is produced for integers with $k=s\geq 2$ bits, and let's prove the same for $k=s+1$.

Let $c_1, \dots, c_{s+1}$ denote the columns. We view the column $c_s$ as formed by blocks of size 2, where the $i$-th block consists of numbers $2^s+2i-2$ and $2^s+2i-1$ is some order ($i=1,2,\dots,2^{s-1}$). It is easy to see that each column $c_j$ for $j<s$ represents a permutation of the same blocks.

Replacing $i$-th block in $c_s$ with a single number $2^{s-1}+i-1$ and using the induction assumption for $k=s$, we conclude that $c_1$ forms a Gray code unless we have a change in the numbers parity (i.e., unequal least significant bits) when we go from some block to the next one. It remains to show that such change in parity never happens.

Call a block positive is the numbers in it appears in their natural order, and call it negative otherwise. Absence of the parity change between adjacent blocks in $c_1$ means that positive and negative blocks in it alternate. Below we show that this property holds already for $c_{s-1}$, and then it trivially propagates to all $c_j$ with $j<s-1$ (including $c_1$).

Let $(\tau_i)_{i\geq 0}$ denotes Thue-Morse sequence. By construction, the $i$-th block in $c_s$ is positive iff $\tau_{i-1}=1$. Furthermore, the $i$-th block in $c_s$ retains its position in $c_{s-1}$ iff $\tau_{\lfloor(i-1)/2\rfloor}=1$, otherwise its position shifts by 1 (down or up). Since $\tau_{i-1} + \tau_{\lfloor(i-1)/2\rfloor} \equiv i-1\pmod{2}$, we get that in $c_{s-1}$ positive blocks appear at odd positions and negative blocks appear at even positions, i.e. positive and negative blocks alternate. QED