login
Fixed point of the morphism 0 -> 10, 1 -> 1011.
5

%I #31 Sep 09 2019 01:08:02

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

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

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

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

%C From __Michel Dekking_, Sep 08 2019: (Start)

%C A short proof of Mathar's conjecture can be obtained by using the fact that sigma and tau are conjugate morphisms. For all words w one has

%C tau(w) = 1^{-1} sigma(w) 1.

%C The proof is again by induction. Suppose that

%C (A) : 0 sigma^n(0) = tau^n(0) 0

%C holds. Then, choosing w = tau^n(0):

%C tau^{n+1}(0) 0 = tau(tau^n(0)) 0 =

%C 1^{-1} sigma(tau^n(0)) 1 0 =

%C 1^{-1} sigma(0 sigma^n(0) 0^{-1}) 10 =

%C 1^{-1} 10 sigma^{n+1}(0) 0^{-1}1^{-1} 10 =

%C 0 sigma^{n+1}.

%C So (A) holds for n+1.

%C (End)

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

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

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

%F From _Michel Dekking_, Feb 05 2018: (Start)

%F Proof of this conjecture: let sigma be the morphism 0 -> 10, 1 -> 1011, and let tau be the morphism 0 -> 01, 1 -> 0111, which has A284893 as a fixed point. It clearly suffices to prove the relation, for all n=1,2,3,...:

%F (A) : 0 sigma^n(0) = tau^n(0) 0

%F To prove such a thing one needs a second relation, for all n=1,2,3,...:

%F (B) : 0 sigma^n(1) 0^{-1} = tau^n(0) tau^n(1) [tau^n(0)]^{-1}

%F Here 0^{-1} and [tau^n(0)]^{-1} are the free group inverses of 0 and tau^n(0).

%F For n=1, we do indeed have:

%F (a) 0 sigma(10) = 0101110 = 0101110 = tau(01)0

%F (b) 0 sigma(1) 0^{-1} tau(0) = 010111 = tau(0)tau(1).

%F Using the induction hypothesis with (A) and (B) in the second line, one obtains

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

%F = tau^n(0) tau^n(1) [tau^n(0)]^{-1} tau^n(0) 0

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

%F Similarly,

%F 0 sigma^{n+1}(1) 0^{-1}

%F = 0 sigma^n(1) 0^{-1} 0 sigma^n(0) 0^{-1} 0 sigma^n(11) 0^{-1}

%F = tau^n(0)tau^n(1)[tau^n(0)]^{-1} tau^n(0) 0 0^{-1}

%F tau^n(0) tau^n(11) [tau^n(0)]^{-1}

%F = tau^{n+1}(0) tau^{n+1}(1) [tau^n(1)]^{-1}[tau^n(0)]^{-1}

%F = tau^{n+1}(0) tau^{n+1}(1) [tau^{n+1}(0)]^{-1}. (End)

%e 0 -> 10-> 1011 -> 10111010111011.

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

%t u = Flatten[Position[s, 0]]; (* A285342 *)

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

%t u/2 (* A285344)

%Y Cf. A285342, A285343, A285344.

%K nonn,easy

%O 1

%A _Clark Kimberling_, Apr 25 2017