Theorem 15 (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]} 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, 1], {[1, 1]}, {a, b, a - b}]}, [1, 1]] 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, [0]], [%1, [0, 1]], [%1, [1, 1, 1, 1, 1, 1, 1, 1, 1]], [%1, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]], [[0, 1, 1], [[1], m[1]]], [[0, 1, 1], [[1], m[1]], [0, 1, 1, 0, 1, 1, 0, 1, 1]], [[0, 1, 1], [[1], m[1]], [0, 1, 1, 0, 1, 1, 0, 1, 1, 0]]} %1 := [[0, 1, 1], m[1]] For the regular expression, [[[2, 1, 1], m[1]]] applying the rule, we see, by induction that the last two elements are m[1] [a + b, a (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] -(1/2) = 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], m[1]], [2]] applying the rule, we see, by induction that the last two elements are m[1] m[1] [a (1/2) , -a - b + a (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 0 = 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], m[1]], [2, 1]] applying the rule, we see, by induction that the last two elements are m[1] [-a - b + a (1/2) , a + b] 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] -3 + 2 (1/2) = 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], m[1]], [1, 1, 1, 1, 1, 1, 1, 1, 1]] applying the rule, we see, by induction that the last two elements are 171 m[1] 85 a 85 b 171 a 171 b 341 m[1] [--- a (1/2) + ---- + ----, ----- + ----- + --- a (1/2) ] 256 256 256 512 512 512 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] 343 (1/2) - 513 = 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], m[1]], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] applying the rule, we see, by induction that the last two elements are 171 a 171 b 341 m[1] 683 m[1] 341 a 341 b [----- + ----- + --- a (1/2) , ---- a (1/2) + ----- + -----] 512 512 512 1024 1024 1024 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] -1023 + 681 (1/2) = 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]]] applying the rule, we see, by induction that the last two elements are 2 a m[1] /3 a \ m[1] [--- + b/3 - 2/3 a (-1/2) + 4/3 |--- + b/2| (-1/2) , 3 \ 4 / 2 a m[1] /3 a \ m[1] --- + b/3 + 1/3 a (-1/2) - 2/3 |--- + b/2| (-1/2) ] 3 \ 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[1] -4 + (-1/2) = 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]], [2, 1, 1, 2, 1, 1, 2, 1, 1]] applying the rule, we see, by induction that the last two elements are 2 a m[1] /3 a \ m[1] [--- + b/3 - 2/3 a (-1/2) + 4/3 |--- + b/2| (-1/2) , 3 \ 4 / a b m[1] /3 a \ m[1] ---- + ---- + 1/24 a (-1/2) - 1/12 |--- + b/2| (-1/2) ] 12 24 \ 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[1] -6 + 5 (-1/2) = 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]], [2, 1, 1, 2, 1, 1, 2, 1, 1, 2]] applying the rule, we see, by induction that the last two elements are a b m[1] /3 a \ m[1] [---- + ---- + 1/24 a (-1/2) - 1/12 |--- + b/2| (-1/2) , 12 24 \ 4 / 7 a 7 b 17 m[1] 17 /3 a \ m[1] - --- - --- + -- a (-1/2) - -- |--- + b/2| (-1/2) ] 12 24 24 12 \ 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[1] -5 + 5 (-1/2) = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!)