

A178525


The sum of the costs of all nodes in the Fibonacci tree of order n.


3



0, 0, 3, 8, 22, 49, 104, 208, 403, 760, 1406, 2561, 4608, 8208, 14499, 25432, 44342, 76913, 132808, 228416, 391475, 668840, 1139518, 1936513, 3283392, 5555424, 9381699, 15815528, 26618518, 44733745, 75073256, 125827696, 210642643
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n1 and whose right subtree is the Fibonacci tree of order n2; each of the Fibonacci trees of order 0 and 1 is defined as a single node. In a Fibonacci tree the cost of a left (right) edge is defined to be 1 (2). The cost of a node in a Fibonacci tree is defined to be the sum of the costs of the edges that form the path from the root to this node.
A178525 is the 1sequence of reduction of the odd number sequence (2n1) by x^2 > x+1; as such it is related to 0sequence of this reduction, A192304. See A192232 for definition of "ksequence of reduction of [sequence] by [substitution]".  Clark Kimberling, Jun 27 2011


REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, AddisonWesley, Reading, MA, 1998, p. 417.


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168178.
Index entries for linear recurrences with constant coefficients, signature (3,1,3,1,1).


FORMULA

a(n) = 3 + (2*n3)*F(n1) + (2*n5)*F(n), where F(k)=A000045(k) are the Fibonacci numbers.
a(n) = a(n1) + a(n2) + 2*F(n+1) + 2*F(n1)  3 (n>=2), F(0)=0, F(1)=0.
G.f.: z^2*(3z+z^2)/((1z)*(1zz^2)^2).


MAPLE

with(combinat): seq(3+(2*n3)*fibonacci(n1)+(2*n5)*fibonacci(n), n = 0 .. 32);


MATHEMATICA

Table[3 +(2*n3)*Fibonacci[n1] +(2*n5)*Fibonacci[n], {n, 0, 40}] (* G. C. Greubel, Jan 30 2019 *)


PROG

(PARI) a(n) = 3+(2*n3)*fibonacci(n1) + (2*n5)*fibonacci(n); \\ Michel Marcus, Jan 21 2019
(MAGMA) [3 +(2*n3)*Fibonacci(n1) +(2*n5)*Fibonacci(n): n in [0..40]]; // G. C. Greubel, Jan 30 2019
(Sage) [3 +(2*n3)*fibonacci(n1) +(2*n5)*fibonacci(n) for n in range(40)] # G. C. Greubel, Jan 30 2019
(GAP) List([0..40], n > 3 +(2*n3)*Fibonacci(n1) +(2*n5)*Fibonacci(n)); # G. C. Greubel, Jan 30 2019


CROSSREFS

Cf. A000045, A094584, A178521.
Sequence in context: A156291 A111136 A063937 * A266187 A328002 A202192
Adjacent sequences: A178522 A178523 A178524 * A178526 A178527 A178528


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Jun 15 2010


STATUS

approved



