login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178521 The cost of all leaves in the Fibonacci tree of order n. 3
0, 0, 3, 7, 17, 35, 70, 134, 251, 461, 835, 1495, 2652, 4668, 8163, 14195, 24565, 42331, 72674, 124354, 212155, 360985, 612743, 1037807, 1754232, 2959800, 4985475, 8384479, 14080601, 23614931, 39556030, 66181310, 110608187, 184670693, 308030923, 513334855 (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 leaf of a Fibonacci tree is defined to be the sum of the costs of the edges that form the path from the root to this leaf.

REFERENCES

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

LINKS

Colin Barker, 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 (2,1,-2,-1).

FORMULA

a(n) = n*F(n+1) - F(n), where F(k) = A000045(k).

G.f.: x^2*(x+3)/(x^2+x-1)^2. - Colin Barker, Nov 11 2012

a(n) = Sum_{k=1..n-1} F(k) * L(n-k+1) where F(n) = A000045(n), L(n) = A000032(n). - Gary Detlefs, Dec 29 2012

a(n) = (n-1)*F(n) + n*F(n-1). - Bruno Berselli, Dec 06 2013

a(0) = 0, a(n) = A023607(n-1) + A099920(n-1). - Collin Berman, Dec 12 2016

a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4). - Wesley Ivan Hurt, Dec 14 2016

a(n) = (n+1)*F(n+1) - F(n+2). - Bruno Berselli, Jul 26 2017

a(n) = (2^(-1-n)*(2*sqrt(5)*((1-sqrt(5))^n - (1+sqrt(5))^n) + (-(1-sqrt(5))^n*(-5+sqrt(5)) + (1+sqrt(5))^n*(5+sqrt(5)))*n))/5. - Colin Barker, Jul 26 2017

MAPLE

with(combinat); seq(n*fibonacci(n+1)-fibonacci(n), n = 0 .. 35);

MATHEMATICA

Table[n Fibonacci[n + 1] - Fibonacci[n], {n, 0, 40}]  (* Harvey P. Dale, Apr 21 2011 *)

Table[(n - 1) Fibonacci[n] + n Fibonacci[n - 1], {n, 0, 40}] (* Bruno Berselli, Dec 06 2013 *)

PROG

(PARI) concat(vector(2), Vec(x^2*(x+3)/(x^2+x-1)^2 + O(x^50))) \\ Colin Barker, Jul 26 2017

CROSSREFS

Cf. A000045, A136376.

Sequence in context: A168582 A192958 A219293 * A034482 A114100 A260677

Adjacent sequences:  A178518 A178519 A178520 * A178522 A178523 A178524

KEYWORD

nonn,easy

AUTHOR

Emeric Deutsch, Jun 14 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 June 19 00:37 EDT 2021. Contains 345125 sequences. (Running on oeis4.)