Theorem 5 (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]
| 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] m[1] m[1]
[a (-1) + b (-1) , 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] m[1] m[1]
-(-1) + 1 - (-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] m[1] m[1]
[a (-1/2) , a (-1) + b (-1) - 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] m[1]
((-1/2) - 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], 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/2) , -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]
(-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, 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 m[1] 85 m[1]
[--- a (-1/2) + --- a (-1) + --- b (-1) ,
256 256 256
171 m[1] 171 m[1] 341 m[1]
--- a (-1) + --- b (-1) + --- a (-1/2) ]
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] m[1] m[1] m[1]
(-1) (-1/2) - 342 (-1/2) - 341 (-1) + 512 = 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 m[1] 171 m[1] 341 m[1]
[--- a (-1) + --- b (-1) + --- a (-1/2) ,
512 512 512
683 m[1] 341 m[1] 341 m[1]
---- a (-1/2) + ---- a (-1) + ---- b (-1) ]
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] m[1] m[1] m[1]
-683 (-1) - (-1) (-1/2) - 682 (-1/2) + 1024 = 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]
14 - 17 (-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 (-1/2) + 5 = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)