cp's OEIS Frontend

From Michel Dekking, Mar 17 2020: (Start)

This sequence is a morphic sequence, i.e., the letter-to-letter image of the fixed point of a morphism mu. In fact, one can take the alphabet {A,B,C,D} with the morphism

mu: A->AB, B->CD, C->ABCD, D->CD,

and the letter-to-letter map lambda defined by

lambda: A->0, B->1, C->2, D->1.

Then (a(n)) = lambda(x), where x = ABCDABCDCD... is the unique fixed point of the morphism mu.

How does one see this? The infinite Fibonacci word

x_F = A003849 = 0100101001001....

can be written as a concatenation of the two words 01 and 001.

In fact, if beta is the Fibonacci morphism 0->01, 1->0, then beta(01)=010, beta(001)=01010, from which this can be read off.

This can also be found in Lemma 23 in Allouche and Dekking, which gives, moreover, that if we define the morphism g on the alphabet {a,b} by

g(a) = ab, g(b) =abb

then a(n) = delta(x_G(n)), where

x_G = ababbababb...

is the unique fixed point of g, and delta is the map

delta(a) = 01, delta(b) = 21.

In my paper "Morphic words,..." such a map delta is called a decoration.

It is well-known that decorated fixed points are morphic sequences, and the 'natural' algorithm to achieve this splits a in AB, and b in CD. This gives the morphism mu on the alphabet {A,B,C,D}, and the letter-to-letter map lambda.

We next prove the first conjecture by Kimberling. We easily see from the form of mu that the letters B and D occur, and only occur, at even positions in the fixed point x of mu. Since lambda(B)=lambda(D)=1, and A and C are not mapped to 1, it follows immediately that the positions of 1 in (a(n)) are given by A005843 = (2n).

For a proof of Kimberling's second conjecture, note that a(n)=2 iff x(n)=C, where x is the fixed point of mu. The return words of C in x are CD and CDAB. Coding these two return words by their lengths, mu induces a descendant morphism tau given by

tau(2) = 24, tau(4) = 244.

We see that tau is just an alphabet change of the morphism g. Let t = 2424424244... be the unique fixed point of tau. It is well-known (see, e.g., Lemma 12 in "Morphic words,..."), that t = 2 x_F, where x_F = x_F(4,2) now is the Fibonacci word on the alphabet {4,2}. The partial sums of x_F(4,2) are equal to the generalized Beatty sequence V given by

V(n) = 2*floor(n*phi) + 1,

according to Lemma 8 in the Allouche and Dekking paper.

This proves Kimberling's conjecture, provided we give the sequence A130568 offset 1, as we should.

(End)