Theorem 59 (by Shalosh B. Ekhad) Consider the following recurrence if x[n-1], x[n] mod 2 equal, resp. , 1, 1, then, x[n + 1] = 1/2 x[n - 1] - 1/2 x[n] if x[n-1], x[n] mod 2 equal, resp. , 1, 0, then, x[n + 1] = -x[n - 1] + x[n] if x[n-1], x[n] mod 2 equal, resp. , 0, 1, then, x[n + 1] = -x[n - 1] + x[n] if x[n-1], x[n] mod 2 equal, resp. , 0, 0, then, x[n + 1] = 1/2 x[n - 1] - 1/2 x[n] based on empirical observation, we are lead to the following Conjecture: Every trajectory of the rule F with gcod(x[-1],x[0])=1 eventually ends in one of the following orbits {[0, 0], [1, -1], [1, 1, 0, -1, -1, 0]} We have the following bounds for the general term, x[n] If x[n-1] mod, 2, equals , 1, and x[n] mod, 2, equals, 1, then | x[n] | <= | x[-1] | + | x[0] | If x[n-1] mod, 2, equals , 1, and x[n] mod, 2, equals, 2, then | x[n] | <= | x[-1] | + | x[0] | If x[n-1] mod, 2, equals , 2, and x[n] mod, 2, equals, 1, then | x[n] | <= 2 | x[-1] | + 2 | x[0] | This can presumbly be proved rigorously by an appropriate scheme but it is not implemented yet Without loss of generality we can have the first two elements as, [a, -b] Because of the above inequalities, it is possible to prove (rigorously!) that the only words in the alphabet, {0,1} that a trajectory of the rule modulo 2, can have are {[[0], [[1], m[1]]], [[0], [[1], m[1]], [0]], [[0], [[1], m[1]], [0, 1]], [[0], [[1], m[1]], [0, 1, 1]]} For the regular expression, [[2], [[1], m[1]]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [2/3 (-a - b) (-1) + 1/3 b (-1) + 4/3 (-a - b) (1/2) m[1] m[1] m[1] - 4/3 b (1/2) , -2/3 (-a - b) (-1) - 1/3 b (-1) m[1] m[1] - 2/3 b (1/2) + 2/3 (-a - b) (1/2) ] By equating the first two elements with the last two elements we see that a and b must be 0 (or one of the above-found orbits) unless the following condition holds m[1] m[1] m[1] 2 (-1) (1/2) - (-1) - 1 = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!) For the regular expression, [[2], [[1], m[1]], [2]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-2/3 (-a - b) (-1) - 1/3 b (-1) - 2/3 b (1/2) m[1] m[1] m[1] + 2/3 (-a - b) (1/2) , -4/3 (-a - b) (-1) - 2/3 b (-1) m[1] m[1] - 2/3 (-a - b) (1/2) + 2/3 b (1/2) ] By equating the first two elements with the last two elements we see that a and b must be 0 (or one of the above-found orbits) unless the following condition holds m[1] m[1] m[1] 2 (-1) (1/2) - 2 (1/2) - 1 = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!) For the regular expression, [[2], [[1], m[1]], [2, 1]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-4/3 (-a - b) (-1) - 2/3 b (-1) - 2/3 (-a - b) (1/2) m[1] m[1] m[1] + 2/3 b (1/2) , -2/3 (-a - b) (-1) - 1/3 b (-1) m[1] m[1] + 4/3 b (1/2) - 4/3 (-a - b) (1/2) ] By equating the first two elements with the last two elements we see that a and b must be 0 (or one of the above-found orbits) unless the following condition holds m[1] m[1] ((-1) - 1) (2 (1/2) + 1) = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!) For the regular expression, [[2], [[1], m[1]], [2, 1, 1]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-2/3 (-a - b) (-1) - 1/3 b (-1) + 4/3 b (1/2) m[1] m[1] m[1] - 4/3 (-a - b) (1/2) , -1/3 (-a - b) (-1) - 1/6 b (-1) m[1] m[1] + 1/3 (-a - b) (1/2) - 1/3 b (1/2) ] By equating the first two elements with the last two elements we see that a and b must be 0 (or one of the above-found orbits) unless the following condition holds m[1] m[1] -((-1) - 2) (2 (1/2) - 1) = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!)