login
Fixed point of the morphism 0 -> 10, 1 -> 1100.
6

%I #21 Jan 31 2024 16:57:03

%S 1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,0,

%T 1,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,

%U 0,0,1,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1

%N Fixed point of the morphism 0 -> 10, 1 -> 1100.

%C This is a 3-automatic sequence. See Allouche et al. link. - _Michel Dekking_, Oct 05 2020

%H Clark Kimberling, <a href="/A285345/b285345.txt">Table of n, a(n) for n = 1..10000</a>

%H J.-P. Allouche, F. M. Dekking, and M. Queffélec, <a href="https://arxiv.org/abs/2010.00920">Hidden automatic sequences</a>, arXiv:2010.00920 [math.NT], 2020.

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%F Conjecture: a(n) = A284905(n+1). - _R. J. Mathar_, May 08 2017

%F From _Michel Dekking_, Jan 26 2024: (Start)

%F Proof of Mathar's conjecture: let alpha be the morphism 0 -> 10, 1 -> 1100, and let beta be the morphism 0 -> 01, 1 -> 1001, which has A284905 as its fixed point starting with 0. Note that alpha^n(0) tends to (a(n)) as n tends to infinity because alpha(0) starts with 1. It therefore suffices to prove the relation

%F (A) : 0 alpha^n(0) = beta^n(0) 0 for all n=1,2,3,...

%F To prove such a thing one uses the fact that alpha and beta are conjugate morphisms, i.e., there exists a word u such that

%F (B) beta(w) = u^{-1} alpha(w) u.

%F Here u^{-1} is the free group inverse of u.

%F We have in this case u:=1, and it suffices to prove (B) for the words w=0, and w=1. Indeed:

%F beta(0) = 01 = 1^{-1} 10 1 = 1^{-1} alpha(0) 1,

%F beta(1) = 1001 = 1^{-1} 1100 1 = 1^{-1} alpha(1) 1.

%F Next, we prove (A). For n=1, we do have 0 alpha(0) = 010 = beta(0) 0.

%F Suppose (A) has been proved till n. Then

%F 0 alpha^{n+1}(0) = 1^{-1} 10 alpha^{n+1}(0) (10)^{-1} 10

%F = 1^{-1} alpha(0) alpha^{n+1}(0) (alpha(0))^{-1} 10

%F = 1^{-1} alpha(0 alpha^n(0) 0^{-1} ) 10

%F = 1^{-1} alpha(beta^n(0) ) 1 0

%F = beta(beta^n(0)) 0 = beta^{n+1}(0) 0.

%F Here we used (B) with w = beta^n(0) in line three, and the induction hypothesis in line four. (End)

%e 0 -> 10-> 1100 -> 110011001010 -> ...

%t s = Nest[Flatten[# /. {0 -> {1, 0}, 1 -> {1, 1, 0, 0}}] &, {0}, 10]; (* this sequence *)

%t Flatten[Position[s, 0]]; (* A285346 *)

%t Flatten[Position[s, 1]]; (* A285347 *)

%Y Cf. A284346, A285347.

%K nonn,easy

%O 1

%A _Clark Kimberling_, Apr 25 2017