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

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) ?

• Yes, there are $2^{n+1}$ code words of length $n+1$. But make sure to use your inductive hypothesis that the claim is true for $n$. That is: you need to show that if you have gray codes for all words of length $n$, you can use that to create Gray codes for al words of length $n+1$ Commented Apr 17, 2020 at 19:13
• How could I accomplish this? I have used n=1 ? Just claiming this in a hypothesis? And use this in the induction step? Commented Apr 17, 2020 at 19:16
• The $n=1$ case does not really come into play for the inductive step. That is,you don;t go from $1$ to $2$, because even if you show that, you then have to show that you can go from $2$ to $3$, etc. So, what you want to show is that in general, you can go from $n$ to $n+1$. And yes, for that, you can just claim as the inductive hypothesis that you have Gray codes for all words of length $n$. Commented Apr 17, 2020 at 19:19

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.