# Why Are The First and Last Entries of a Binary Reflected Gray Code Sequence Adjacent?

Some Information on Gray Codes

If you're rusty or unfamiliar with Binary Reflected Gray Code, but want to try and help, here is a youtube tutorial explaining what they are:

https://www.youtube.com/watch?v=eGgkcf62xl8

My Question

Looking at some basic Reflected Binary Gray Code sequences: We can see that the first and last entry of each sequence differ only by one bit. Wikipedia referred to this as the "cyclic property" of gray codes, but did so without citation or further elaboration. I understand why two entries right beside each other would differ by 1 bit, but not why the first and last would. Could anyone explain this to me?

## 1 Answer

The binary reflected Gray code is defined inductively:

• The binary reflected Gray code of length $0$ is $G^0 = ()$ (empty list).
• Let $G^n = (g^n_1, \ldots, g^n_{2^n})$ be the binary reflected Gray code of length $n$. Then the binary reflected Gray code of length $n+1$ is

$$G^{n+1} = (0g^n_1, \ldots, 0g^n_{2^n}, 1g^n_{2^n}, \ldots, 1g^n_1).$$

For example:

\begin{align} G^0 &= ()\\ G^1 &= (0, 1)\\ G^2 &= (00, 01, 11, 10)\\ G^3 &= (000, 001, 011, 010, 110, 111, 101, 100) \end{align}

As to your question, the first and last entries of $G^{n+1}$ are defined as $0g_1^n$ and $1g^n_1$, which differ only in the first position (i.e., only by $1$ bit).