Theorem 13 (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], [3, 1, 2, -1], [1, -1, 0, -1, 1, 0]} We have the following bounds for the general term, x[n] | x[n] | <= | x[-1] | + | x[0] | This is proved (rigorously!) by the existence of the following scheme [{[[1, 1], {[1, 1], [1, 2]}, {a, b}], [[1, 2], {[2, 1]}, {a, b, a - b, 2 b - a}], [[2, 1], {[1, 1]}, {a, b, a - b}]}, [1, 2]] 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, [[1], m[2]], [0, 1, 1, 0, 1]]} %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 5 a 5 b m[1] m[1] [--- + --- - 8/9 b (1/4) + 4/9 a (1/4) 9 9 /2 a 2 b m[1] m[1]\ m[2] - 4/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] 5 a 5 b + 4/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-1/2) , --- + --- 9 9 m[1] m[1] - 8/9 b (1/4) + 4/9 a (1/4) /2 a 2 b m[1] m[1]\ m[2] + 2/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] - 2/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-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[2] m[2] m[1] -3 + 4 (1/4) - (-1/2) + 3 (-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 5 a 5 b m[1] m[1] [--- + --- - 8/9 b (1/4) + 4/9 a (1/4) 9 9 /2 a 2 b m[1] m[1]\ m[2] + 2/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] - 2/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-1/2) , /2 a 2 b m[1] m[1]\ m[2] -2 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] + 2 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-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[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 /2 a 2 b m[1] m[1]\ m[2] [-2 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] 5 a 5 b + 2 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-1/2) , --- + --- 9 9 m[1] m[1] - 8/9 b (1/4) + 4/9 a (1/4) /2 a 2 b m[1] m[1]\ m[2] + 8/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] - 8/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-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[2] m[1] ((-1/2) + 2) (-7 + 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 5 a 5 b m[1] m[1] [--- + --- - 8/9 b (1/4) + 4/9 a (1/4) 9 9 /2 a 2 b m[1] m[1]\ m[2] + 8/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] - 8/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-1/2) , /2 a 2 b m[1] m[1]\ m[2] 1/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] 5 a 5 b - 1/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-1/2) + --- + --- 18 18 m[1] m[1] - 4/9 b (1/4) + 2/9 a (1/4) ] 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] 7 (-1/2) - 19 (-1/2) (1/4) - 13 + 16 (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 /2 a 2 b m[1] m[1]\ m[2] [1/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] 5 a 5 b - 1/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-1/2) + --- + --- 18 18 m[1] m[1] 5 a 5 b m[1] - 4/9 b (1/4) + 2/9 a (1/4) , --- + --- - 4/9 b (1/4) 18 18 m[1] + 2/9 a (1/4) /2 a 2 b m[1] m[1]\ m[2] + 7/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] - 7/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-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[2] m[2] m[1] m[1] -(-1/2) - (-1/2) (1/4) - 3 + 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, 1, 1, 2, 1]] applying the rule, we see, by induction that the last two elements are 5 a 5 b m[1] m[1] [--- + --- - 4/9 b (1/4) + 2/9 a (1/4) 18 18 /2 a 2 b m[1] m[1]\ m[2] + 7/3 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] - 7/3 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-1/2) , /2 a 2 b m[1] m[1]\ m[2] -2 |--- + --- - 2/3 b (1/4) + 1/3 a (1/4) | (-1/2) \ 3 3 / m[1] m[1] m[2] + 2 (a/2 + b/2 - b (1/4) + 1/2 a (1/4) ) (-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[2] m[1] -((-1/2) - 1) (-13 + 4 (1/4) ) = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!)