# Proof of Gray code

Prove that for every $$n \in \mathbb N$$ with $$n \geq 1$$ a $$1$$-step binary code $$C_n$$ for the inteval $$[0, 2^n −1]$$ with code words of length $$n$$ exists.

I have to prove it using induction.

• Welcome to SE. What have you tried so far? – Behrad Moniri Apr 14 '19 at 16:32
• Tried to find a function for the 1 step binary. Just struggled to define a function for that came to the point of 0 0, 0 1, 1 0 , 1 1. is 0 and 1 with added 0 and 1. And frustrating don't know if it's kind of a right way to solve the answer. – Rack Cloud Apr 14 '19 at 16:40

Given an $$n$$ bit code, an $$n+1$$ bit code consists of all the strings prefixed with a $$0$$ and all the strings prefixed with $$1$$. Start with the code with the $$0$$ prefix, which gets you half way there. All the rest start with $$1$$, so the first code with $$1$$ has to match on all of he other bits. Going from the last to the first you will have a change in the first bit, so again all the others have to match. Can you see how to construct it?
• For example, a two bit code is $00,01,11,10$. Put a zero in front of each, then put a one in front in reverse order and you get $000,001,011,010,110,111,101,100$ which works. You need to show this process always works. – Ross Millikan Apr 15 '19 at 0:38