OFFSET
0,1
COMMENTS
Conjecture: a(n) is the number of letters (0's and 1's) in the n-th iteration of the mapping 00->0010, 1->001, starting with 00; see A288173.
From Michel Dekking, Feb 22 2020: (Start)
Proof of this conjecture.
We know (see A288173) that A288173 can be generated as a decoration delta(t) of the fixed point t of the morphism alpha given by
alpha(A) = AB, alpha(B) = AC, alpha(C) = ABB.
Here delta is the morphism
delta(A) = 001, delta(B) = 0001, delta(C) = 00001.
Looking at the proof, we see that we have in more detail that the n-th iterate of SR starting with 00 equals the decoration of the (n-1)-th iterate of alpha starting with A, with a suffix 0 added.
For example,
SR(00) = 0010 = delta(A)0, SR^2(00) = 00100010 = delta(alpha(A))0.
This implies that the total number of letters (0's and 1's) minus 1 in the n-th iterate of SR is equal to the vector/matrix/vector product
(3,4,5) M^(n-1) (1,0,0)^T,
where (1,0,0)^T is the transpose of (1,0,0), and M is the incidence matrix of the morphism alpha, so M equals
|1 1 1 |
|1 0 2 |
|0 1 0 |.
The characteristic polynomial of M is equal to chi(u) = u^3-u^2-3*u+1. It follows therefore from the Cayley-Hamilton theorem that the sequence of lengths minus 1 satisfies the linear recursion
a(n+3) = a(n+2) + 3*a(n+1) - a(n).
This is not the conjectured recursion a(n+4) = 2*a(n+3) +2* a(n+2) - 4*a(n+1) + a(n) for A288176.
However, if we substitute one of the three a(n+2)'s by a(n+2) = a(n+3) -3*a(n+1) + a(n) in the shifted equation
a(n+4) = a(n+3) + 3*a(n+2) - a(n+1),
then we obtain the conjectured recursion.
This proves the conjecture (where one uses that the constant sequence (1,1,1,...) satisfies the conjectured recursion). (End)
LINKS
Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (2,2,-4,1).
FORMULA
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3) + a(n-4), where a(0) = 2, a(1) = 4, a(2) = 8, a(3) = 16.
G.f.: (-2 + 4*x^2)/((-1 + x) (1 - x - 3*x^2 + x^3)).
MATHEMATICA
LinearRecurrence[{2, 2, -4, 1}, {2, 4, 8, 16}, 40]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Jun 07 2017
STATUS
approved