A276677 Number of squares added at the n-th generation of a symmetric (with 45-degree angles), non-overlapping Pythagoras tree.

1, 2, 4, 8, 16, 28, 48, 76, 120, 180, 272, 396, 584, 836, 1216, 1724, 2488, 3508, 5040, 7084, 10152, 14244, 20384, 28572, 40856, 57236, 81808, 114572, 163720, 229252, 327552, 458620, 655224, 917364, 1310576, 1834860, 2621288, 3669860, 5242720, 7339868

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

With an offset of 4, auxiliary sequence C(n) is equal to A077866: C(n+4) = A077866(n).

Partial sums give A276647.

Sequence in context: A260881 A089055 A305122 * A112128 A208933 A227036

Adjacent sequences: A276674 A276675 A276676 * A276678 A276679 A276680

Keyword

nonn,easy

Author

Ernst van de Kerkhof, Sep 13 2016

Status

approved