login
Number of squares after the n-th generation in a symmetric (with 45-degree angles) non-overlapping Pythagoras tree.
2

%I #62 Oct 10 2022 07:56:37

%S 1,3,7,15,31,59,107,183,303,483,755,1151,1735,2571,3787,5511,7999,

%T 11507,16547,23631,33783,48027,68411,96983,137839,195075,276883,

%U 391455,555175,784427,1111979,1570599,2225823,3143187,4453763,6288623,8909911,12579771

%N Number of squares after the n-th generation in a symmetric (with 45-degree angles) non-overlapping Pythagoras tree.

%C Non-overlapping is to be understood as: any two different squares in the tree can never share more than one side, disallowing area overlap. In branches where an area overlap is about to occur, growth is terminated.

%H Colin Barker, <a href="/A276647/b276647.txt">Table of n, a(n) for n = 0..1000</a>

%H Ernst van de Kerkhof, <a href="/A276647/a276647.png">Illustration of a(6)</a>

%H "QuantumKiwi", <a href="https://www.youtube.com/watch?v=cUwhMvd61do">A Year in the Life of a Pythagoras Tree</a>, YouTube, (2008).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Pythagoras_tree_(fractal)">Pythagoras tree (fractal)</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-5,6,-2).

%F Theorem: a(n) = 20*2^floor(n/2) + 28*2^floor((n-1)/2) - (2*n^2+10*n+33).

%F From _Colin Barker_, Sep 20 2016: (Start)

%F G.f.: (1+x)^2*(1-2*x+2*x^2) / ((1-x)^3*(1-2*x^2)).

%F a(n) = 3*a(n-1)-a(n-2)-5*a(n-3)+6*a(n-4)-2*a(n-5) for n>4.

%F a(n) = (-25+2^((n-1)/2)*(24-24*(-1)^n+17*sqrt(2)+17*(-1)^n*sqrt(2))-4*(1+n)-2*(1+n)*(2+n)). Therefore:

%F a(n) = 17*2^(n/2+1)-2*n^2-10*n-33 for n even.

%F a(n) = 3*2^((n+7)/2)-2*n^2-10*n-33 for n odd. (End)

%t TableForm[Table[{n, 20 * 2^Floor[n/2] + 28*2^Floor[(n-1)/2] - (2n^2 + 10n + 33)}, {n, 0, 100, 1}], TableSpacing -> {1, 5}]

%t LinearRecurrence[{3,-1,-5,6,-2},{1,3,7,15,31},50] (* _Harvey P. Dale_, May 07 2019 *)

%o (PARI) Vec((1+x)^2*(1-2*x+2*x^2)/((1-x)^3*(1-2*x^2)) + O(x^50)) \\ _Colin Barker_, Sep 20 2016

%Y Partial sums of A276677.

%K nonn,easy

%O 0,2

%A _Ernst van de Kerkhof_, Sep 13 2016