OFFSET
0,2
COMMENTS
The auxiliary sequence C(n), which appears in the recurrence relation for a(n), is defined as the number of collisions (squares touching each other, halting tree growth at that point) in generation n.
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Ernst van de Kerkhof, Illustration of a(7)
Index entries for linear recurrences with constant coefficients, signature (2,1,-4,2).
FORMULA
a(0) = 1, a(n) = 2*a(n-1) - 4*C(n-1), where:
C(0) = 0; for n >= 1, C(n) = C(n-1) + 2^(floor(n/2)-1) - 1. Also:
C(0) = 0; for n >= 1, C(n) = 2^floor(n/2) + 2^floor((n-1)/2) - (n+1).
a(0) = 1; for n >= 1, a(n) = 6*2^floor(n/2) + 8*2^floor((n-1)/2) - (4*n+8).
All formulas are proved.
From Colin Barker, Sep 20 2016: (Start)
G.f.: (1 + x)^2*(1 - 2*x + 2*x^2) / ((1 - x)^2*(1 - 2*x^2)).
a(n) = 2*a(n-1) + a(n-2) - 4*a(n-3) + 2*a(n-4) for n>4.
a(n) = -4+2^((n-1)/2)*(7-7*(-1)^n+5*sqrt(2)+5*(-1)^n*sqrt(2))-4*(1+n) for n>0. Therefore:
a(n) = 5*2^(n/2+1)-8-4*n for n>0 and even;
a(n) = 7*2^((n+1)/2)-8-4*n for n>0 and odd. (End)
MATHEMATICA
TableForm[Table[{n, 6*2^Floor[n/2] + 8*2^Floor[(n-1)/2] - (4n + 8)}, {n, 1, 100, 1}], TableSpacing -> {1, 5}]
LinearRecurrence[{2, 1, -4, 2}, {1, 2, 4, 8, 16}, 70] (* Harvey P. Dale, Jan 21 2019 *)
PROG
(PARI) Vec((1+x)^2*(1-2*x+2*x^2)/((1-x)^2*(1-2*x^2)) + O(x^50)) \\ Colin Barker, Sep 20 2016
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ernst van de Kerkhof, Sep 13 2016
STATUS
approved