Proving that for every n there exists one step codes from 0 to 2^(n)-1 (Gray Code)

Question

Prove that for every n ∈ N with n ≥ 1 exists a one step binary code Cn for the number interval [0..2 n −1] with code words of length n.

I have the hint of complete induction.

So my start would be that for n = 1 it exists

This would be

0

1

Now for n+1

I dont't know how to display this now? I had 2 code words for 1 For n+1 is should be 2^(n+1) ?

Answer 1

Say you have a Gray sequence for words with length $n$: $a_1,\dots,a_{2^n}$. From this you can construct a Gray sequence at length $n+1$ as $$0a_1,0a_2,\dots,0a_{2^n},1a_{2^n},\dots,1a_2,1a_1$$ This accomplishes the inductive step – strong (complete) induction is not needed.

This operation of flipping the sequence and adding $0$s and $1$s to each side is why the Gray code is sometimes called the reflected binary code.