Proof of Gray code

Question

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.

Answer 1

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?