Gray codes: a cyclic list of all bit strings with one change at a time

Construction. For $n=2$: $00,01,11,10$ works.

Suppose $g_1,\dots,g_m$ ($m=2^{n-1}$) is a valid cyclic list for length $n-1$. Define for length $n$ the list
$$0g_1,\,0g_2,\,\dots,\,0g_m,\,1g_m,\,1g_{m-1},\,\dots,\,1g_1.$$

It contains every string once. The first half contains all strings starting with $0$, the second half all those starting with $1$, each once.

Consecutive strings differ in one position.
- Inside the first half, $0g_i$ and $0g_{i+1}$ differ exactly where $g_i,g_{i+1}$ do.
- Inside the second half, same argument.
- At the middle, $0g_m$ and $1g_m$ differ only in the first position.
- Closing the cycle, $1g_1$ and $0g_1$ differ only in the first position.

By induction the list exists for every $n\ge2$.

Explicit form. The $k$-th string ($k=0,\dots,2^n-1$) can be taken to be the binary expansion of $k\oplus\lfloor k/2\rfloor$. Consecutive strings differ in one bit; and $k=2^n-1$ gives $10\cdots0$, which differs from the string $0$ for $k=0$ in one bit.

Remark. This is a Hamiltonian cycle in the $n$-dimensional cube graph. Gray codes are used in rotary encoders.

Lesson. "Reflect and prefix" constructions work for recursive structures; check the seams.