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