A047860 a(n) = T(3,n), array T given by A047858.

1, 5, 14, 34, 78, 174, 382, 830, 1790, 3838, 8190, 17406, 36862, 77822, 163838, 344062, 720894, 1507326, 3145726, 6553598, 13631486, 28311550, 58720254, 121634814, 251658238, 520093694, 1073741822, 2214592510, 4563402750

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

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

Examples

			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
		

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

Crossrefs

n-th difference of a(n), a(n-1), ..., a(0) is (4, 5, 6, ...).

First differences of A027993.

Programs

Magma

[2^(n-1)*(n+6)-2: n in [0..30]]; // Vincenzo Librandi, Sep 28 2011

Mathematica

LinearRecurrence[{5,-8,4},{1,5,14},30] (* Harvey P. Dale, Sep 29 2012 *)

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

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