%I #16 Oct 13 2018 13:12:49
%S 0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,
%T 0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,
%U 0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0
%N Fixed point of the mapping 00->0010, 1->010, starting with 00.
%C From _Michel Dekking_, Oct 12 2018: (Start)
%C Here is a proof of the conjecture on the sequence of lengths 2, 4, 8, 18, 38, 80, ... of the iterates of the mapping (see also A288206). We note first that the mapping SR: 00->0010, 1->010, is an algorithmic procedure given by StringReplace in Mathematica. This makes it hard in general to describe iterates of it. However, here is an analysis of what happens in this particular case. Let
%C H:=100, T:=1000, Z:=00, E1:=100, E2:=10.
%C Then
%C SR(H) = 0100010 = 0 T H 0^{-1},
%C SR(T) = 01000100 = 0 T T 0^{-1},
%C SR(Z) = 0010 = Z H 0^{-1},
%C SR(E1) = 0100010 = 0 T E2,
%C SR(E2) = 0100 = 0 E1.
%C Let sigma be the morphism on the alphabet {H,T,Z,E1,E2} given by
%C sigma(Z)=ZH, sigma(H)=TH, sigma(T)=TT, sigma(E1)= T E2, sigma(E2)= E1.
%C Then, because the 0's at the beginning of SR(H), SR(T), SR(E1) and SR(E2) always cancel, we have
%C sigma^n(Z E2) = SR^{n+1}(Z) for n=0,1,2,...,
%C Examples:
%C Z E2 = 0010 = SR(00),
%C sigma(Z E2) = ZH E1 = 00100100,
%C sigma^2(Z E2) = ZHTHT E2 = 001001000100100010.
%C From this it follows that
%C (a(n)) = delta(x),
%C where x = (x(n)) is the infinite word with x(1)=Z fixed by sigma, i.e., sigma(x)=x, and delta is the 'decoration' morphism
%C delta(H):=100, delta(T):=1000, delta(Z):=00.
%C Note that sigma is a reducible morphism, and that E1 and E2 do not occur in the fixed point x (they only occur at the end of the SR^n(00)).
%C We also proved that the number of letters (Z's, H's, T's, E1's, and E2's} in the n-th iterate of SR is equal to the vector/matrix/vector product
%C (2,3,4,3,2) M^n (1,0,0,0,1)^T,
%C where (1,0,0,0,1)^T is the transpose of (1,0,0,0,1), and M is the incidence matrix of the morphism sigma, i.e., M equals
%C |1 0 0 0 0|
%C |1 1 0 0 0|
%C |0 1 2 1 0|
%C |0 0 0 0 1|
%C |0 0 0 1 0|
%C The characteristic polynomial of M is equal to chi(u) = u^5-4u^4+4u^3+2u^2-5u+2. It follows therefore from the Cayley-Hamilton theorem that the sequence of lengths satisfies the linear recursion
%C a(n+5) = 4*a(n+4) - 4*a(n+3) - 2*a(n+2) + 5*a(n+1) - 2*a(n).
%C This is not the conjectured recursion a(n+4) = 3*a(n+3) - a(n+2) - 3*a(n+1) + 2*a(n) from A288206.
%C However, if we add this recursion to the shifted recursion a(n+5) = 3*a(n+4) - a(n+3) - 3*a(n+2) + 2*a(n+1), then we obtain the recursion above. This proves the conjecture.
%C (End)
%C From the analysis above it follows that the frequencies of 0 and 1 in (a(n)) exist and are equal to 3/4 and 1/4. - _Michel Dekking_, Oct 12 2018
%H Clark Kimberling, <a href="/A288203/b288203.txt">Table of n, a(n) for n = 1..10000</a>
%e Iterates, starting with 00:
%e 00
%e 0010
%e 00100100
%e 001001000100100010
%e 00100100010010001000100010010001000100
%t s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
%t w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "010"}]
%t Table[w[n], {n, 0, 8}]
%t st = ToCharacterCode[w[11]] - 48 (* A288203 *)
%t Flatten[Position[st, 0]] (* A288204 *)
%t Flatten[Position[st, 1]] (* A288205 *)
%t Table[StringLength[w[n]], {n, 1, 35}] (* A288206 conjectured *)
%Y Cf. A288204, A288205, A288206.
%K nonn,easy
%O 1
%A _Clark Kimberling_, Jun 07 2017
|