login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 n-1 and whose right subtree is the Fibonacci tree of order n-2; 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 1-sequence of reduction of the odd number sequence (2n-1) by x^2 -> x+1; as such it is related to 0-sequence of this reduction, A192304. See A192232 for definition of "k-sequence of reduction of [sequence] by [substitution]". - Clark Kimberling, Jun 27 2011

REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, 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, 168-178.

Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

FORMULA

a(n) = 3 + (2*n-3)*F(n-1) + (2*n-5)*F(n), where F(k)=A000045(k) are the Fibonacci numbers.

a(n) = a(n-1) + a(n-2) + 2*F(n+1) + 2*F(n-1) - 3 (n>=2), F(0)=0, F(1)=0.

G.f.: z^2*(3-z+z^2)/((1-z)*(1-z-z^2)^2).

MAPLE

with(combinat): seq(3+(2*n-3)*fibonacci(n-1)+(2*n-5)*fibonacci(n), n = 0 .. 32);

MATHEMATICA

Table[3 +(2*n-3)*Fibonacci[n-1] +(2*n-5)*Fibonacci[n], {n, 0, 40}] (* G. C. Greubel, Jan 30 2019 *)

PROG

(PARI) a(n) = 3+(2*n-3)*fibonacci(n-1) + (2*n-5)*fibonacci(n); \\ Michel Marcus, Jan 21 2019

(MAGMA) [3 +(2*n-3)*Fibonacci(n-1) +(2*n-5)*Fibonacci(n): n in [0..40]]; // G. C. Greubel, Jan 30 2019

(Sage) [3 +(2*n-3)*fibonacci(n-1) +(2*n-5)*fibonacci(n) for n in range(40)] # G. C. Greubel, Jan 30 2019

(GAP) List([0..40], n -> 3 +(2*n-3)*Fibonacci(n-1) +(2*n-5)*Fibonacci(n)); # G. C. Greubel, Jan 30 2019

CROSSREFS

Cf. A000045, A094584, A178521.

Sequence in context: A156291 A111136 A063937 * A266187 A202192 A027211

Adjacent sequences:  A178522 A178523 A178524 * A178526 A178527 A178528

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Jun 15 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 22 16:39 EDT 2019. Contains 325224 sequences. (Running on oeis4.)