login
A288176
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.
2
2, 4, 8, 16, 34, 72, 156, 336, 730, 1580, 3432, 7440, 16154, 35040, 76060, 165024, 358162, 777172, 1686632, 3659984, 7942706, 17236024, 37404156, 81169520, 176145962, 382250364, 829518728, 1800123856, 3906429674, 8477282512, 18396447676, 39921865536
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)
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
Cf. A288173.
Sequence in context: A367660 A288260 A006210 * A096812 A006981 A003427
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Jun 07 2017
STATUS
approved