Theorem 35 (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, 0, -1, -1, 1, 0, 1], [1, 1, -1, 0, -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 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, [0]], [%1, [1]], [%1, [0, 1]], [%1, [1, 0]], [%1, [0, 1, 1]], [%1, [1, 0, 1]], [%1, [0, 1, 1, 0]], [%1, [1, 0, 1, 1]], [%1, [0, 1, 1, 0, 1]], [%1, [1, 0, 1, 1, 0]], [%1, [0, 1, 1, 0, 1, 1]], [%1, [1, 0, 1, 1, 0, 1]], [%1, [0, 1, 1, 0, 1, 1, 0]]} %1 := [[0, 1, 1, 1], m[1]] For the regular expression, [[[2, 1, 1, 1], m[1]]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] m[1] [a (-1) + b (-1) - 2 a (-1/4) , 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[1] m[1] m[1] m[1] -(-1) + 2 (-1/4) + 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]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] m[1] [a (-1/4) , -1/2 a (-1) - 1/2 b (-1) + 1/2 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[1] m[1] -((-1/4) - 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, 1], m[1]], [2]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] m[1] [a (-1/4) , a (-1) + b (-1) - 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[1] m[1] ((-1/4) - 1) ((-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, 1, 1], m[1]], [1, 2]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-1/2 a (-1) - 1/2 b (-1) + 1/2 a (-1/4) , m[1] m[1] m[1] 3/2 a (-1/4) - 1/2 a (-1) - 1/2 b (-1) ] 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] m[1] 2 (-1) + (-1) (-1/4) - (-1/4) + 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]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] m[1] m[1] [a (-1) + b (-1) - a (-1/4) , a (-1) + b (-1) ] 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] m[1] -2 (-1) - (-1) (-1/4) + (-1/4) + 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, 1, 1], m[1]], [1, 2, 1]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [3/2 a (-1/4) - 1/2 a (-1) - 1/2 b (-1) , m[1] m[1] m[1] -a (-1) - b (-1) + 2 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[1] m[1] m[1] m[1] -(-1) (-1/4) - 3 (-1/4) + 3 (-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]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] m[1] m[1] [a (-1) + b (-1) , -a (-1) - b (-1) + 1/2 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[1] m[1] 2 - (-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, 2, 1, 1]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-a (-1) - b (-1) + 2 a (-1/4) , m[1] m[1] m[1] -7/4 a (-1/4) + 3/4 a (-1) + 3/4 b (-1) ] 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] m[1] (-1) - (-1) (-1/4) - 8 (-1/4) + 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]], [2, 1, 1, 2]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] m[1] [-a (-1) - b (-1) + 1/2 a (-1/4) , 1/2 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[1] m[1] m[1] m[1] 2 (-1) + (-1) (-1/4) - (-1/4) + 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]], [1, 2, 1, 1, 2]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-7/4 a (-1/4) + 3/4 a (-1) + 3/4 b (-1) , m[1] m[1] m[1] -1/4 a (-1) - 1/4 b (-1) + 1/4 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[1] m[1] m[1] m[1] (-1/4) (-1) + 7 (-1/4) - 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]], [2, 1, 1, 2, 1]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] m[1] [1/2 a (-1/4) , -a (-1) - b (-1) + 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[1] m[1] -((-1/4) - 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, 1, 1], m[1]], [1, 2, 1, 1, 2, 1]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-1/4 a (-1) - 1/4 b (-1) + 1/4 a (-1/4) , m[1] m[1] m[1] -3/2 a (-1/4) + 1/2 a (-1) + 1/2 b (-1) ] 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] m[1] -(-1) - (-1/4) (-1) - (-1/4) + 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]], [2, 1, 1, 2, 1, 1]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-a (-1) - b (-1) + a (-1/4) , m[1] m[1] m[1] -3/4 a (-1/4) + 1/2 a (-1) + 1/2 b (-1) ] 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] m[1] 2 (-1) - (-1/4) (-1) - 4 (-1/4) + 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]], [2, 1, 1, 2, 1, 1, 2]] applying the rule, we see, by induction that the last two elements are m[1] m[1] m[1] [-3/4 a (-1/4) + 1/2 a (-1) + 1/2 b (-1) , m[1] m[1] m[1] -1/2 a (-1) - 1/2 b (-1) + 1/4 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[1] m[1] m[1] (-1/4) (-1) + 3 (-1/4) + 4 = 0 and this can never happen, unless it (possibly) coincides with the the above-found orbits (you prove it!)