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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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

Examples

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

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

Crossrefs

Cf. A000045, A000051, A006479, A175722.

Cf. A001629.

Programs

Haskell

a006478 n = a006478_list !! (n-3)
a006478_list = scanl1 (+) $ drop 2 a001629_list
-- Reinhard Zumkeller, Sep 12 2015

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

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 */

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

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