A192232 -id:A192232 - 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).

A192068 a(n) = Fibonacci(2*n) - (n mod 2).

Original entry on oeis.org

0, 3, 7, 21, 54, 144, 376, 987, 2583, 6765, 17710, 46368, 121392, 317811, 832039, 2178309, 5702886, 14930352, 39088168, 102334155, 267914295, 701408733, 1836311902, 4807526976, 12586269024, 32951280099, 86267571271, 225851433717, 591286729878

Offset: 1

Clark Kimberling, Jun 26 2011

nonn

Previous name was: 1-sequence of reduction of Lucas sequence by x^2 -> x+1.

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

			(See A192243.)

Cf. A000032, A000045, A192243, A192068.

Partial sums of A081714.

a := n -> combinat[fibonacci](2*n)-(n mod 2):
seq(a(n), n=1..29); # Peter Luschny, Mar 10 2015

c[n_] := LucasL[n];
Table[c[n], {n, 1, 15}]
q[x_] := x + 1; p[0, x_] := 1;
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,
   30}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 30}]  (* A192243 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 30}]  (* A192068 *)
(* Peter J. C. Moses, Jun 26 2011 *)
Table[Fibonacci[2n]-Mod[n,2],{n,30}] (* Harvey P. Dale, Jul 11 2020 *)

Empirical g.f. and recurrence: x^2*(3-2*x)/(1-3*x+3*x^3-x^4), a(n) = 3*a(n-1) - 3*a(n-3) + a(n-4). - Colin Barker, Feb 08 2012

a(n) = Fibonacci(2*n) - (n mod 2). - Peter Luschny, Mar 10 2015

New name from Peter Luschny, Mar 10 2015

A192238 Constant term in the reduction of the polynomial x(x+1)(x+2)...(x+n-1) by x^2 -> x+1.

Original entry on oeis.org

1, 0, 1, 6, 37, 256, 1999, 17490, 169895, 1816320, 21205745, 268547510, 3667187645, 53722014720, 840455448415, 13985762375970, 246675543859855, 4596826887347200, 90249727067243425, 1861971659969854950, 40274219840308939925

Offset: 1

Clark Kimberling, Jun 26 2011

nonn

See A192232.

Cf. A192232, A192239.

q[x_] := x + 1;
p[0, x_] := 1; p[1, x_] := x;
p[n_, x_] := (x + n) p[n - 1, x] /; 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,
   20}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 20}]  (* A192238 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 20}]  (* A192239 *)
(* Peter J. C. Moses, Jun 25 2011 *)

Conjecture: a(n) +2*(-n+1)*a(n-1) +(n^2-3*n+1)*a(n-2)=0. - R. J. Mathar, May 04 2014

E.g.f.: 2 - (cosh((sqrt(5)/2)*log(1-x)) + (3/sqrt(5))*sinh((sqrt(5)/2)*log(1-x)))/(1-x)^(3/2). - Fabian Pereyra, Oct 28 2024

A192240 Constant term in the reduction of the polynomial (x+3)^n by x^2 -> x+1.

Original entry on oeis.org

1, 3, 10, 37, 149, 636, 2813, 12695, 57922, 265809, 1223521, 5640748, 26026505, 120137307, 554669594, 2561176781, 11826871933, 54615158940, 252210521317, 1164706900879, 5378632571666, 24838652091993, 114705606355625, 529714071477452

Offset: 0

Clark Kimberling, Jun 26 2011

nonn

See A192232.

Robert Israel, Table of n, a(n) for n = 0..1498

Cf. A192232.

seq(eval(rem((x+3)^n,x^2-x-1,x),x=0),n=0..50); # Robert Israel, Mar 14 2023

q[x_] := x + 1;
p[n_, x_] := (x + 3)^n;
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,
     30}];
Table[Coefficient[Part[t, n], x, 0], {n, 30}]  (* A192240 *)
Table[Coefficient[Part[t, n], x, 1], {n, 30}]  (* A099453 *)
(* Peter J. C. Moses, Jun 26 2011 *)

Empirical g.f. and recurrence: (1-4*x)/(1-7*x+11*x^2). a(n) = 7*a(n-1) - 11*a(n-2). - Colin Barker, Feb 09 2012
Proof of recurrence: if r(n) == (x+3)^n mod (x^2-x-1), then r(n+j) == (x+1)^(n+j) mod (x^2 - x - 1). Now r(n+2) - 7*r(n+1) + 11*r(n) == ((x+3)^2 - 7*(x+3) + 11)*r(n) == 0 mod (x^2-x-1) since (x+3)^2 - 7*(x+3) + 11 = x^2 - x - 1. - Robert Israel, Mar 14 2023
a(n) = Sum_{i=0..n} (-1)^i*Fibonacci(i+1)*binomial(n,i)*4^(n-i) (conjecture). - Rigoberto Florez, Mar 25 2020

Offset corrected by Robert Israel, Mar 14 2023

A192244 0-sequence of reduction of triangular number sequence by x^2 -> x+1.

Original entry on oeis.org

1, 1, 7, 17, 47, 110, 250, 538, 1123, 2278, 4522, 8812, 16911, 32031, 59991, 111263, 204593, 373370, 676800, 1219440, 2185251, 3896796, 6917892, 12231192, 21544717, 37819885, 66179335, 115464893, 200906723, 348688838

Offset: 1

Clark Kimberling, Jun 26 2011

nonn

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

Cf. A192232, A192245.

c[n_] := n (n + 1)/2;  (* triangular numbers, A000217 *)
Table[c[n], {n, 1, 15}]
q[x_] := x + 1; p[0, x_] := 1;
p[n_, x_] :=  p[n - 1, x] + (x^n)*c[n]
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, 30}]
Table[Coefficient[Part[t,n],x,0],{n,1,30}] (* A192244 *)
Table[Coefficient[Part[t,n],x,1],{n,1,30}] (* A192245 *)
(* Peter J. C. Moses, Jun 26 2011 *)

Empirical g.f.: x*(1-3*x+6*x^2-3*x^3)/(1-x)/(1-x-x^2)^3. - Colin Barker, Feb 10 2012

A192248 0-sequence of reduction of binomial coefficient sequence B(n,4)=A000332 by x^2 -> x+1.

Original entry on oeis.org

1, 1, 16, 51, 191, 569, 1619, 4259, 10694, 25709, 59743, 134818, 296798, 639518, 1352498, 2813750, 5769200, 11676395, 23358450, 46239770, 90667076, 176244326, 339887026, 650715076, 1237467151, 2338753519, 4394813644, 8214444389

Offset: 1

Clark Kimberling, Jun 27 2011

nonn

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

Cf. A192232, A192249, A192069.

c[n_] :=  n (n + 1) (n + 2) (n + 3)/24;  (* binomial B(n,4), A000332 *)
Table[c[n], {n, 1, 15}]
q[x_] := x + 1;
p[0, x_] := 1; 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}]  (* A192248 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]  (* A192249 *)
Table[Coefficient[Part[t, n]/5, x, 1], {n, 1, 40}]  (* A192069 *)
(* by Peter J. C. Moses, Jun 20 2011 *)

Conjecture: G.f.: -x*(-1+5*x-20*x^2+30*x^3-25*x^4+8*x^5) / ( (x-1)*(x^2+x-1)^5 ). - R. J. Mathar, May 04 2014

A192250 0-sequence of reduction of central binomial coefficient sequence by x^2 -> x+1.

Original entry on oeis.org

1, 1, 7, 27, 167, 923, 5543, 32999, 200309, 1221329, 7503033, 46301793, 286971677, 1784658077, 11131825877, 69611130917, 436270168817, 2739539507957, 17232530582057, 108564692241257, 684901029237677, 4326215549824277, 27357682806703397

Offset: 1

Clark Kimberling, Jun 27 2011

nonn

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

Cf. A192232, A192251, A192070.

c[n_] := (2 n)!/(n! n!); (* central binomial coefficients, A000984 *)
Table[c[n], {n, 0, 15}]
q[x_] := x + 1;
p[0, x_] := 1; p[n_, x_] := p[n - 1, x] + (x^n)*c[n]
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,
   30}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 30}]  (* A192250 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 30}]  (* A192251 *)
Table[Coefficient[Part[t, n]/2, x, 1], {n, 1, 30}]  (* A192070 *)
(* by Peter J. C. Moses, Jun 20 2011 *)

Conjecture: (n-1)*(n-2)*a(n) -(5*n-7)*(n-2)*a(n-1) -2*(2*n-3)*(3*n-8)*a(n-2) +4*(2*n-3)*(2*n-5)*a(n-3)=0. - R. J. Mathar, May 04 2014

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

Original entry on oeis.org

1, 1, 10, 26, 76, 184, 429, 941, 1994, 4094, 8208, 16128, 31169, 59393, 111818, 208330, 384620, 704408, 1280925, 2314525, 4158346, 7432606, 13223040, 23424576, 41335201, 72679969, 127373194, 222545306, 387732844, 673762744

Offset: 1

Clark Kimberling, Jun 27 2011

nonn

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

c[n_] := n^2;  (* A000290 *)
Table[c[n], {n, 1, 15}]
q[x_] := x + 1;
p[0, x_] := 1; 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,
   30}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 30}]  (* A192254 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 30}]  (* A192255 *)
(* Peter J. C. Moses, Jun 20 2011 *)

Empirical g.f.: x*(1-3*x+9*x^2-6*x^3+2*x^4)/(1-x)/(1-x-x^2)^3. - Colin Barker, Feb 10 2012

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

Original entry on oeis.org

1, 1, 6, 13, 31, 64, 129, 249, 470, 869, 1583, 2848, 5073, 8961, 15718, 27405, 47535, 82080, 141169, 241945, 413366, 704261, 1196831, 2029248, 3433441, 5798209, 9774534, 16451149, 27646975, 46397824

Offset: 1

Clark Kimberling, Jun 27 2011

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

Cf. A192232, A178525.

c[n_] := 2 n - 1; (* odd numbers, A005408 *)
Table[c[n], {n, 1, 15}]
q[x_] := x + 1;
p[0, x_] := 1; 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,
   30}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 30}]  (* A192304 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 30}]  (* A178525 *)
(* Peter J. C. Moses, Jun 20 2011 *)

Empirical g.f.: x*(1-2*x+4*x^2-x^3)/(1-3*x+x^2+3*x^3-x^4-x^5). - Colin Barker, Feb 08 2012

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

Original entry on oeis.org

2, 2, 10, 21, 49, 100, 200, 384, 722, 1331, 2419, 4344, 7726, 13630, 23882, 41601, 72101, 124412, 213844, 366300, 625522, 1065247, 1809575, 3067056, 5187674, 8758010, 14760010, 24835629, 41727577, 70012756, 117321824, 196365624, 328299986, 548309195, 914865307

Offset: 1

Clark Kimberling, Jun 27 2011

nonn

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

Cf. A192232, A192310.

c[n_] := 3 n - 1;
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}]  (* A192309 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]  (* A192310 *)
(* Peter J. C. Moses, Jun 20 2011 *)

Empirical g.f.: x*(2-4*x+6*x^2-x^3)/(1-3*x+x^2+3*x^3-x^4-x^5). - Colin Barker, Feb 09 2012

More terms from Jason Yuen, Aug 23 2025

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

A192068 a(n) = Fibonacci(2*n) - (n mod 2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A192238 Constant term in the reduction of the polynomial x(x+1)(x+2)...(x+n-1) by x^2 -> x+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A192240 Constant term in the reduction of the polynomial (x+3)^n by x^2 -> x+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A192244 0-sequence of reduction of triangular number sequence by x^2 -> x+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A192248 0-sequence of reduction of binomial coefficient sequence B(n,4)=A000332 by x^2 -> x+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A192250 0-sequence of reduction of central binomial coefficient sequence by x^2 -> x+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

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

Views

Author