After reading this question words "Gray code", "Hypercube graph", "Haming Distance" and "Even length cycles" are coming in mind.

Now if you are thinking why Hypercube graph has chromatic no = 2 or Even length cycle then refer -->

https://math.stackexchange.com/questions/227681/how-to-find-chromatic-number-of-the-hypercube-q-n

Chromatic number is 2 so maximum independent set size is $2^{n-1}$.