A288176 - OEIS

%I #17 Apr 07 2020 22:16:08

%S 2,4,8,16,34,72,156,336,730,1580,3432,7440,16154,35040,76060,165024,

%T 358162,777172,1686632,3659984,7942706,17236024,37404156,81169520,

%U 176145962,382250364,829518728,1800123856,3906429674,8477282512,18396447676,39921865536

%N 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.

%C 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.

%C From _Michel Dekking_, Feb 22 2020: (Start)

%C Proof of this conjecture.

%C 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

%C       alpha(A) = AB, alpha(B) = AC, alpha(C) = ABB.

%C Here delta is the morphism

%C       delta(A) = 001, delta(B) = 0001, delta(C) = 00001.

%C 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.

%C For example,

%C       SR(00) = 0010 = delta(A)0, SR^2(00) = 00100010 = delta(alpha(A))0.

%C 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

%C       (3,4,5) M^(n-1) (1,0,0)^T,

%C 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

%C       |1 1 1 |

%C       |1 0 2 |

%C       |0 1 0 |.

%C 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

%C       a(n+3) = a(n+2) + 3*a(n+1) - a(n).

%C 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.

%C 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

%C         a(n+4) = a(n+3) + 3*a(n+2) - a(n+1),

%C then we obtain the conjectured recursion.

%C This proves the conjecture (where one uses that the constant sequence (1,1,1,...) satisfies the conjectured recursion). (End)

%H Clark Kimberling, <a href="/A288176/b288176.txt">Table of n, a(n) for n = 0..2000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-4,1).

%F 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.

%F G.f.: (-2 + 4*x^2)/((-1 + x) (1 - x - 3*x^2 + x^3)).

%t LinearRecurrence[{2, 2, -4, 1}, {2, 4, 8, 16}, 40]

%Y Cf. A288173.

%K nonn,easy

%O 0,1

%A _Clark Kimberling_, Jun 07 2017