TAOCP 7.2.1.1 Exercise 52
The previous argument fails only because it does not properly justify two key facts: (i) the projection onto the first $j$ coordinates is indeed surjective, and (ii) how this surjectivity forces a low...
Section 7.2.1.1: Generating All n-Tuples
Exercise 52. [M20] [M20] Prove that if the transition counts of an n-bit Gray cycle satisfy c0 ≤c1 ≤ · · · ≤cn−1, we must have c0 + · · · + cj−1 ≥2j, with equality when j = n.
Verified: yes
Solve time: 3m12s
The previous argument fails only because it does not properly justify two key facts: (i) the projection onto the first $j$ coordinates is indeed surjective, and (ii) how this surjectivity forces a lower bound on the number of projected transitions. Once these are repaired cleanly, the proof becomes straightforward.
Correct Solution
Let
$$ v_0, v_1, \ldots, v_{2^n-1}, v_{2^n}=v_0 $$
be an $n$-bit Gray cycle, so consecutive vertices differ in exactly one coordinate and every $n$-bit vertex appears exactly once.
For each coordinate $i$, let $c_i$ be the number of transitions in which bit $i$ flips. Let $L_j = c_0 + c_1 + \cdots + c_{j-1}$.
Fix $1 \le j \le n$, and consider the projection $\pi_j(v)$ onto the first $j$ coordinates. The projected sequence
$$ \pi_j(v_0), \pi_j(v_1), \ldots, \pi_j(v_{2^n}) $$
forms a closed walk in the $j$-dimensional hypercube $Q_j$. A step contributes to this projected walk exactly when one of the first $j$ bits changes, so the length of the projected walk is precisely $L_j$.
Surjectivity of the projection
Every $j$-bit string $x \in {0,1}^j$ appears as the projection of at least one vertex in the cycle. Indeed, the full vertex $(x,0,\ldots,0) \in {0,1}^n$ is a valid vertex of the $n$-cube, and since the cycle is Hamiltonian, it visits every vertex exactly once. Hence that vertex appears in the cycle, and its projection is exactly $x$.
Therefore, the projected walk visits all $2^j$ vertices of $Q_j$.
Lower bound on $L_j$
The projected walk is a closed walk with $L_j$ edges, hence $L_j$ vertices in its cyclic listing (counting repetitions, with the first vertex repeated at the end).
A walk of length $L_j$ can contain at most $L_j$ distinct vertices, since each step introduces at most one new vertex in the sequence. Since all $2^j$ vertices of $Q_j$ must appear among these vertices, we obtain
$$ L_j \ge 2^j. $$
Thus,
$$ c_0 + c_1 + \cdots + c_{j-1} \ge 2^j. $$
Equality when $j=n$
For $j=n$, the projection is the original cycle itself. The cycle has exactly $2^n$ edges, so
$$ c_0 + c_1 + \cdots + c_{n-1} = 2^n. $$
Hence equality holds when $j=n$.
Conclusion
For every $1 \le j \le n$,
$$ c_0 + c_1 + \cdots + c_{j-1} \ge 2^j, $$
with equality at $j=n$. ∎