|
%I #30 Jan 21 2019 15:46:37
%S 1,2,4,8,16,28,48,76,120,180,272,396,584,836,1216,1724,2488,3508,5040,
%T 7084,10152,14244,20384,28572,40856,57236,81808,114572,163720,229252,
%U 327552,458620,655224,917364,1310576,1834860,2621288,3669860,5242720,7339868
%N Number of squares added at the n-th generation of a symmetric (with 45-degree angles), non-overlapping Pythagoras tree.
%C 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.
%H Colin Barker, <a href="/A276677/b276677.txt">Table of n, a(n) for n = 0..1000</a>
%H Ernst van de Kerkhof, <a href="/A276677/a276677.png">Illustration of a(7)</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-4,2).
%F a(0) = 1, a(n) = 2*a(n-1) - 4*C(n-1), where:
%F C(0) = 0; for n >= 1, C(n) = C(n-1) + 2^(floor(n/2)-1) - 1. Also:
%F C(0) = 0; for n >= 1, C(n) = 2^floor(n/2) + 2^floor((n-1)/2) - (n+1).
%F a(0) = 1; for n >= 1, a(n) = 6*2^floor(n/2) + 8*2^floor((n-1)/2) - (4*n+8).
%F All formulas are proved.
%F From _Colin Barker_, Sep 20 2016: (Start)
%F G.f.: (1 + x)^2*(1 - 2*x + 2*x^2) / ((1 - x)^2*(1 - 2*x^2)).
%F a(n) = 2*a(n-1) + a(n-2) - 4*a(n-3) + 2*a(n-4) for n>4.
%F 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:
%F a(n) = 5*2^(n/2+1)-8-4*n for n>0 and even;
%F a(n) = 7*2^((n+1)/2)-8-4*n for n>0 and odd. (End)
%t TableForm[Table[{n, 6*2^Floor[n/2] + 8*2^Floor[(n-1)/2] - (4n + 8)}, {n, 1, 100, 1}], TableSpacing -> {1, 5}]
%t LinearRecurrence[{2,1,-4,2},{1,2,4,8,16},70] (* _Harvey P. Dale_, Jan 21 2019 *)
%o (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
%Y With an offset of 4, auxiliary sequence C(n) is equal to A077866: C(n+4) = A077866(n).
%Y Partial sums give A276647.
%K nonn,easy
%O 0,2
%A _Ernst van de Kerkhof_, Sep 13 2016
|
