Gray Code for Fibonacci Sequences: identify the starting string and then enumerate these positions in time proportional to the number of strings.

The number of binary strings of length k such that two 1′s are never adjacent in any string equals the k-th Fibonacci number. Further, these strings can be ordered to form a Gray code, which means that successive strings differ in only one position. For example, a Gray code for 3-bit strings is 100 101 001 000 010. The goal is to identify the starting string and then enumerate these positions in time proportional to the number of strings.