OFFSET
0,2
COMMENTS
The Wikipedia article on L-system Example 2 is "Pythagoras Tree" given by the axiom: 0 and rules: 1 -> 11, 0 -> 1[0]0. The length of the n-th string of symbols is a(n). This interpretation leads to a matrix power formula for a(n). - Michael Somos, Jan 12 2015
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..3000
Index entries for linear recurrences with constant coefficients, signature (5,-8,4).
Wikipedia, L-system Example 2: Pythagoras Tree
FORMULA
Main diagonal of the array defined by T(0, j)=j+1 j>=0, T(i, 0)=i+1 i>=0, T(i, j)=T(i-1, j-1)+T(i-1, j)+ 2; a(n)=2^(n-1)*(n+6)-2. - Benoit Cloitre, Jun 17 2003
a(0)=1, a(1)=5, a(2)=14, a(n) = 5*a(n-1)-8*a(n-2)+4*a(n-3). - Vincenzo Librandi, Sep 28 2011
EXAMPLE
G.f. = 1 + 5*x + 14*x^2 + 34*x^3 + 78*x^4 + 174*x^5 + 382*x^6 + 830*x^7 + ...
Using the Pythagoras Tree L-system, a(0) = #0 = 1, a(1) = #1[0]0 = 5, a(2) = #11[1[0]0]1[0]0 = 14. - Michael Somos, Jan 12 2015
MATHEMATICA
LinearRecurrence[{5, -8, 4}, {1, 5, 14}, 30] (* Harvey P. Dale, Sep 29 2012 *)
PROG
(Magma) [2^(n-1)*(n+6)-2: n in [0..30]]; // Vincenzo Librandi, Sep 28 2011
(PARI) {a(n) = if( n<0, 0, [1, 1, 1, 1] * [2, 0, 0, 0; 1, 2, 0, 0; 1, 0, 1, 0; 1, 0, 0, 1]^n * [1, 0, 0, 0]~ )}; /* Michael Somos, Jan 12 2015 */
(PARI) a(n)=([0, 1, 0; 0, 0, 1; 4, -8, 5]^n*[1; 5; 14])[1, 1] \\ Charles R Greathouse IV, Jul 19 2016
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved