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

Author

Ernst van de Kerkhof, Sep 13 2016

Keywords

• nonn
• easy

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

Crossrefs

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

Partial sums give A276647.

Programs

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

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

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)