Is a binary sequence generated by repetition and subsequent digit flipping periodic?

65 Views Asked by At

Consider a binary sequence (i.e. consisting of 1s and 0s), $a_{0}=0$. The members of the sequence are generated by repetition and flipping : $a_{n}$ are all the digits in $a_{n-1}$ followed by all the digits in $a_{n-1}$ but flipped.

The first few members of the sequence would be: $0,01,0110,01101001,011010011001011,011010011001011100101100110100$

Considering this is a very simple generation rule for a very simple type of sequence I expected to find patterns in the resulting infinite sequence (generated by doing the process ad infinitum) but to my surprise there seem to be none (or any local patterns in the partial series). In fact I think the sequence is not periodic, i.e. the number whose decimal expansion has this infinite sequence after the decimal point is irrational.

I have not had much success in proving this, however. Is this really true? If so, how might one approach the proof?

Thank you for your contributions, this really sparked my fascination.

1

There are 1 best solutions below

0
On BEST ANSWER

I believe you have rediscovered the Thue–Morse sequence! (which is never periodic)