0,2

The sub-Fibonacci tree is a rooted tree in which every node with label k and parent node with label g has g child nodes that are assigned labels beginning with k+1 through k+g; the tree starts at generation n=0 with a root node labeled '1' and a child node labeled '2'. The number of nodes in generation n of the sub-Fibonacci tree is A005270(n+2); the maximum label in generation n is Fibonacci(n+2).

Fishburn, Peter C.; Roberts, Fred S.; Elementary sequences, sub-Fibonacci sequences. Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.

The initial nodes of the sub-Fibonacci tree for generations 0..5 are:

gen.0: [1];

gen.1: [2];

gen.2: [3];

gen.3: [4,5];

gen.4: (4)->[5,6,7],(5)->[6,7,8];

gen.5: (5)->[6,7,8,9],(6)->[7,8,9,10],(7)->[8,9,10,11],

(6)->[7,8,9,10,11],(7)->[8,9,10,11,12],(8)->[9,10,11,12,13].

The sum of the labels for nodes in generation n+1 >= 2 is equal to:

a(n+1) = sum (parent label)*(label) over all nodes in generation n

+ sum (parent label)*[label*(label+1)/2] over all nodes in gen. n-1.

For example:

a(2) = 3 = 1*2 + 1*( 1*2/2 );

a(3) = 9 = 2*3 + 1*( 2*3/2 );

a(4) = 39 = 3*(4+5) + 2*( 3*4/2 );

a(5) = 252 = 4*(5+6+7) + 5*(6+7+8) + 3*( 4*5/2 + 5*6/2 );

a(6) = 2361 = 5*(6+7+8+9) + 6*(7+8+9+10) + 7*(8+9+10+11) +

6*(7+8+9+10+11) + 7*(8+9+10+11+12) + 8*(9+10+11+12+13) +

4*( 5*6/2 + 6*7/2 + 7*8/2 ) + 5*( 6*7/2 + 7*8/2 + 8*9/2 ).

Cf. A125051, A005270.

Sequence in context: A064020 A095412 A074428 this_sequence A052828 A012972 A037389

Adjacent sequences: A125049 A125050 A125051 this_sequence A125053 A125054 A125055

nonn

Paul D. Hanna (pauldhanna(AT)juno.com), Nov 19 2006