A006478 a(n) = a(n-1) + a(n-2) + F(n) - 1, a(0) = a(1) = 0, where F() = Fibonacci numbers A000045. (Formerly M2733)

0, 0, 0, 1, 3, 8, 18, 38, 76, 147, 277, 512, 932, 1676, 2984, 5269, 9239, 16104, 27926, 48210, 82900, 142055, 242665, 413376, 702408, 1190808, 2014608, 3401833, 5734251, 9650312, 16216602, 27213182, 45608092, 76345851, 127656829, 213230144, 355817324, 593205284

Offset

0,5

Comments

Partial sums of A001629.

Number of edges in the Fibonacci hypercube FQ(n-2) (defined in the Rispoli and Cosares reference). - Emeric Deutsch, Oct 06 2014

Circuit rank (cyclomatic number) of the n-Fibonacci cube graph. - Eric W. Weisstein, Sep 05 2017

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Carlos Alirio Rico Acevedo and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.

Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Gray codes for Fibonacci q-decreasing words, arXiv:2010.09505 [cs.DM], 2020.

Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.

K. J. Overholt, Efficiency of the Fibonacci search method, Nordisk Tidskr. Informationsbehandling (BIT) 13 (1973), 92-96.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

F. J. Rispoli and S. Cosares, The Fibonacci hypercube, Australasian J. Combinatorics, 40, 2008, 187-196.

Eric Weisstein's World of Mathematics, Circuit Rank

Eric Weisstein's World of Mathematics, Fibonacci Cube Graph

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

Formula

a(n) - a(n-1) = A001629(n-1).

a(n) = 1 + ((n-5)*F(n-1) + (3*n-8)*F(n))/5.

G.f.: x^3/((1-x)*(1-x-x^2)^2). - Simon Plouffe in his 1992 dissertation

a(n) = Sum_{k=0..n-1} Sum_{i=0..k} F(i)*F(k-i). - Benoit Cloitre, Jan 26 2003

a(n) = A175722(-2-n). - Michael Somos, Mar 11 2014

a(n) = 3*a(n-1) - a(n-2) - 3*a(n-3) + a(n-4) + a(n-5). - Eric W. Weisstein, Sep 05 2017

E.g.f.: exp(x) + exp(x/2)*(5*(3*x - 5)*cosh(sqrt(5)*x/2) + sqrt(5)*(5*x - 11)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Jul 24 2022

Example

G.f. = x^3 + 3*x^4 + 8*x^5 + 18*x^6 + 38*x^7 + 76*x^8 + 147*x^9 + 277*x^10 + ...

Maple

A006478 := proc(n)
  1 + ((n-5)*combinat[fibonacci](n-1)+(3*n-8)*combinat[fibonacci](n)) / 5;
end proc:
seq(A006478(n), n=0..20) ; # R. J. Mathar, Jun 12 2018

Mathematica

CoefficientList[Series[x^3/((1 - x) (1 - x - x^2)^2), {x, 0, 50}], x] (* Vincenzo Librandi, Mar 13 2014 *)
LinearRecurrence[{3, -1, -3, 1, 1}, {0, 0, 0, 1, 3, 8}, 20] (* Eric W. Weisstein, Sep 05 2017 *)
Table[1 + (2 (n + 1) Fibonacci[n] + n Fibonacci[n + 1])/5 - Fibonacci[n + 2], {n, 0, 20}] (* Eric W. Weisstein, Sep 05 2017 *)

Prog

(PARI) {a(n) = if( n<0, polcoeff( x^2 / ((1 - x) * (1 + x - x^2)^2) + x * O(x^-n), -n), polcoeff( x^3 / ((1 - x) * (1 - x - x^2)^2) + x * O(x^n), n))}; /* Michael Somos, Mar 11 2014 */
(Haskell)
a006478 n = a006478_list !! (n-3)
a006478_list = scanl1 (+) $ drop 2 a001629_list
-- Reinhard Zumkeller, Sep 12 2015

Crossrefs

Cf. A000045, A000051, A006479, A175722.

Cf. A001629.

Sequence in context: A078409 A036642 A000235 * A104187 A131051 A051633

Adjacent sequences: A006475 A006476 A006477 * A006479 A006480 A006481

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

a(0)-a(2) added and offset changed - N. J. A. Sloane, Jun 19 2021

Programs and b-file adapted by Georg Fischer, Jun 21 2021

Status

approved