A125052 Sum of labels for nodes in generation n of the sub-Fibonacci tree (A125051).

1, 2, 3, 9, 39, 252, 2361, 32077, 631058, 18035534, 751936149, 45973362492, 4144777181393, 554100538432001, 110435083963283354, 32981178674724868365

Offset

0,2

Comments

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).

Links

Table of n, a(n) for n=0..15.

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

Example

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 ).

Crossrefs

Cf. A125051, A005270.

Sequence in context: A095412 A074428 A328436 * A181139 A162093 A052828

Adjacent sequences: A125049 A125050 A125051 * A125053 A125054 A125055

Keyword

nonn

Author

Paul D. Hanna, Nov 19 2006

Extensions

a(10)-a(15) from Alois P. Heinz, May 03 2015

Status

approved