# Cycling sequence of 0 and 1 - is cycle length even?

I hope you can help me with this excersise:

Lets have finite sequence of characters 0 and 1. We are doing following algorithm:
If the sequence starts with 0, we add 00 to the end.
If the sequence starts with 1, we add 1101 to the end.
Then we remove first three characters.

Prove, that if the sequence repeats in cycles, the cycles are of even length.

Proof:
We are changing the length of the sequence, doing n steps, by n. To get to the starting state of the loop, the length has to be changed doing n steps, by -n. The total number of steps is 2n, which is even.

We assume, that if n = n+1, the number of steps is still even.
We are changing the length of the sequence, doing n+1 steps, by n+1. To get to the starting state of the loop, the length has to be changed doing n+1 steps, by -(n+1). The total number of steps is 2n + 2, which is even.

Here are some examples:

In order to create a 2 step loop, we need a sequence starting which some time comes to state
0xx1xx or
1xx0x.
Both these constructions will generate the other one.

To create a 6 step loop, we need
1xx1xx1xx0xx0 or
1xx1xx0xx0xx0x or
1xx0xx0xx0xx1xx or
0xx0xx0xx1xx1xx1 or
0xx0xx1xx1xx1xx or
0xx1xx1xx1xx0x.
They generate the other one in that order.

-
which sequence repeats? The sequence you start with, the sequence of actions you take, the sequence you end up with, or the sequence of finite sequences that you obtain from the process? – Arturo Magidin Dec 6 '10 at 17:27
It is always the same sequence, and the length of the cycle is the number of steps after it returns to its previous state (not necessarily starting state). E.g. starting sequence 10000 -> 10100 -> 001101 ->10100 -> 001101 -> ... and so on. Here the length of cycle is 2. I found that the length is typically 2 or 6. – Ondrej Sotolar Dec 6 '10 at 17:53
Just a nit because you could start with 10100, but shouldn't 10000 to to 001101? – Ross Millikan Dec 6 '10 at 18:25
You are correct, i made a mistake, it should be 10000 -> 001101 -> 10100 -> 001101... – Ondrej Sotolar Dec 6 '10 at 18:36
Your argument is not very clear in my opinion. For one thing, if you "assume $n=n+1$", then you are assuming that $0=1$ and you can prove anything you want. This is really rather simple: if the cycle is length $n$, then after $n$ steps the total change in length must be $0$. If you apply the first rule (which decreases the total length by $1$) $k$ times, and you apply the second rule (which increases the total length by $1$) $\ell$ times, with $n=k+\ell$ being the number of steps in the cycle, then the length changes by $\ell-k$. And since the total change must be $0$... – Arturo Magidin Dec 6 '10 at 22:54