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, 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)

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

Cf. A288173.

Sequence in context: A367660 A288260 A006210 * A096812 A006981 A003427

Adjacent sequences: A288173 A288174 A288175 * A288177 A288178 A288179

Keyword

nonn,easy

Author

Clark Kimberling, Jun 07 2017

Status

approved