A192304 -id:A192304 - cp's OEIS frontend

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

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

Offset: 0

Emeric Deutsch, Jun 15 2010

nonn

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

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

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

Cf. A000045, A094584, A178521.

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

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

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

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

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

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

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

A192305 0-sequence of reduction of (2n) by x^2 -> x+1.

Original entry on oeis.org

2, 2, 8, 16, 36, 72, 142, 270, 504, 924, 1672, 2992, 5306, 9338, 16328, 28392, 49132, 84664, 145350, 248710, 424312, 721972, 1225488, 2075616, 3508466, 5919602, 9970952, 16768960, 28161204, 47229864, 79112062, 132362622, 221216376, 369341388, 616061848, 1026669712, 1709502122, 2844208874, 4728518600, 7855572120

Offset: 1

Clark Kimberling, Jun 27 2011

See A192232 for definition of "k-sequence of reduction of [sequence] by [substitution]".

Cf. A192232, A192306, A192304.

c[n_] := 2 n; (* even numbers, A005843 *)
Table[c[n], {n, 1, 15}]
q[x_] := x + 1;
p[0, x_] := 2; p[n_, x_] := p[n - 1, x] + (x^n)*c[n + 1]
reductionRules = {x^y_?EvenQ -> q[x]^(y/2),
   x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[
  Last[Most[
    FixedPointList[Expand[#1 /. reductionRules] &, p[n, x]]]], {n, 0,
   40}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}]  (* A192305 *)
Table[Coefficient[Part[t, n]/2, x, 0], {n, 1, 40}]  (* A190062 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]  (* A192306 *)
Table[Coefficient[Part[t, n]/2, x, 1], {n, 1, 40}]  (* A122491 *)
(* Peter J. C. Moses, Jun 20 2011 *)

a(n) = 2*A190062(n).

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula