Theorem 106 (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], [5, 3, 4, 1]} 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] | + 2 | x[0] | If x[n-1] mod, 2, equals , 1, and x[n] mod, 2, equals, 2, then | x[n] | <= | x[-1] | + 2 | x[0] | If x[n-1] mod, 2, equals , 2, and x[n] mod, 2, equals, 1, then | x[n] | <= | x[-1] | + | 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 {[%1, [[1], m[2]]], [%1, [[1], m[2]], [0]], [%1, [[1], m[2]], [0, 1]], [%1, [[1], m[2]], [0, 1, 1]], [%1, [[1], m[2]], [0, 1, 1, 0]]} %1 := [[0, 1, 1, 1], m[1]] For the regular expression, [[[2, 1, 1, 1], m[1]], [[1], m[2]]] applying the rule, we see, by induction that the last two elements are 11 a 11 b m[1] 16 m[1] [---- + ---- + 4/15 a (-1/4) - -- b (-1/4) 15 15 15 /4 a 4 b m[1] m[1]\ m[2] - 4/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] 11 a + 4/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) , ---- \10 10 / 15 11 b m[1] 16 m[1] + ---- + 4/15 a (-1/4) - -- b (-1/4) 15 15 /4 a 4 b m[1] m[1]\ m[2] + 2/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] - 2/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) ] \10 10 / 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[2] m[2] m[1] -7 + 12 (-1/4) + (-1/2) + 9 (-1/2) (-1/4) = 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, 1, 1], m[1]], [[1], m[2]], [2]] applying the rule, we see, by induction that the last two elements are 11 a 11 b m[1] 16 m[1] [---- + ---- + 4/15 a (-1/4) - -- b (-1/4) 15 15 15 /4 a 4 b m[1] m[1]\ m[2] + 2/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] - 2/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) , \10 10 / /4 a 4 b m[1] m[1]\ m[2] 2 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] - 2 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) ] \10 10 / 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[2] m[1] 4 ((-1/2) - 1) (-1 + (-1/4) ) = 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, 1, 1], m[1]], [[1], m[2]], [2, 1]] applying the rule, we see, by induction that the last two elements are /4 a 4 b m[1] m[1]\ m[2] [2 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] 11 a - 2 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) , ---- \10 10 / 15 11 b m[1] 16 m[1] + ---- + 4/15 a (-1/4) - -- b (-1/4) 15 15 /4 a 4 b m[1] m[1]\ m[2] + 8/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] - 8/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) ] \10 10 / 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[2] m[1] -(7 (-1/2) - 4) (1 + 4 (-1/4) ) = 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, 1, 1], m[1]], [[1], m[2]], [2, 1, 1]] applying the rule, we see, by induction that the last two elements are 11 a 11 b m[1] 16 m[1] [---- + ---- + 4/15 a (-1/4) - -- b (-1/4) 15 15 15 /4 a 4 b m[1] m[1]\ m[2] + 8/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] - 8/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) , \10 10 / /4 a 4 b m[1] m[1]\ m[2] 7/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] 11 a - 7/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) + ---- \10 10 / 30 11 b m[1] m[1] + ---- + 2/15 a (-1/4) - 8/15 b (-1/4) ] 30 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[2] m[2] m[1] m[1] -15 (-1/2) - 5 (-1/2) (-1/4) - 3 + 8 (-1/4) = 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, 1, 1], m[1]], [[1], m[2]], [2, 1, 1, 2]] applying the rule, we see, by induction that the last two elements are /4 a 4 b m[1] m[1]\ m[2] [7/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] 11 a - 7/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) + ---- \10 10 / 30 11 b m[1] m[1] 11 a 11 b + ---- + 2/15 a (-1/4) - 8/15 b (-1/4) , - ---- - ---- 30 30 30 m[1] m[1] - 2/15 a (-1/4) + 8/15 b (-1/4) /4 a 4 b m[1] m[1]\ m[2] - 1/3 |--- + --- + 1/5 a (-1/4) - 4/5 b (-1/4) | (-1/2) \ 5 5 / /7 a 7 b m[1] m[1]\ m[2] + 1/3 |--- + --- + 3/10 a (-1/4) - 6/5 b (-1/4) | (-1/2) ] \10 10 / 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[2] m[2] m[1] m[1] -3 (-1/2) + 13 (-1/2) (-1/4) + 15 - 10 (-1/4) = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!)