cp's OEIS Frontend

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

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