A006478 -id:A006478 - cp's OEIS frontend

A001629 Self-convolution of Fibonacci numbers.

0, 0, 1, 2, 5, 10, 20, 38, 71, 130, 235, 420, 744, 1308, 2285, 3970, 6865, 11822, 20284, 34690, 59155, 100610, 170711, 289032, 488400, 823800, 1387225, 2332418, 3916061, 6566290, 10996580, 18394910, 30737759, 51310978, 85573315, 142587180, 237387960, 394905492

Offset: 0

N. J. A. Sloane

Number of elements in all subsets of {1,2,...,n-1} with no consecutive integers. Example: a(5)=10 because the subsets of {1,2,3,4} that have no consecutive elements, i.e., {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, the total number of elements is 10. - Emeric Deutsch, Dec 10 2003
If g is either of the real solutions to x^2-x-1=0, g'=1-g is the other one and phi is any 2 X 2-matricial solution to the same equation, not of the form gI or g'I, then Sum'_{i+j=n-1} g^i phi^j = F_n + (A001629(n) - A001629(n-1)g')*(phi-g'I), where i,j >= 0, F_n is the n-th Fibonacci number and I is the 2 X 2 identity matrix... - Michele Dondi (blazar(AT)lcm.mi.infn.it), Apr 06 2004
Number of 3412-avoiding involutions containing exactly one subsequence of type 321.
Number of binary sequences of length n with exactly one pair of consecutive 1's. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 02 2004
For this sequence the n-th term is given by (nF(n+1)-F(n)+nF(n-1))/5 where F(n) is the n-th Fibonacci number. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), Apr 20 2005
If an unbiased coin is tossed n times then there are 2^n possible strings of H and T. Out of these, number of strings with exactly one 'HH' is given by a(n) where a(n) denotes n-th term of this sequence. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), May 04 2005
a(n) is half the number of horizontal dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; a(n+1) = the number of vertical dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; thus 2*a(n)+a(n+1)=n*F(n+1) = the number of dominoes in all domino tilings of a 2 X n rectangle, where F=A000045, the Fibonacci sequence. - Roberto Tauraso, May 02 2005; Graeme McRae, Jun 02 2006
a(n+1) = (-i)^(n-1)*(d/dx)S(n,x)|A049310%20for%20the%20S-polynomials.%20-%20_Wolfdieter%20Lang">{x=i}, where i is the imaginary unit, n >= 1. First derivative of Chebyshev S-polynomials evaluated at x=i multiplied by (-i)^(n-1). See A049310 for the S-polynomials. - _Wolfdieter Lang, Apr 04 2007
For n >= 4, a(n) is the number of weak compositions of n-2 in which exactly one part is 0 and all other parts are either 1 or 2. - Milan Janjic, Jun 28 2010
For n greater than 1, a(n) equals the absolute value of (1 - (1/2 - i/2)*(1 + (-1)^(n + 1))) times the x-coefficient of the characteristic polynomial of the (n-1) X (n-1) tridiagonal matrix with i's along the main diagonal (i is the imaginary unit), 1's along the superdiagonal and the subdiagonal and 0's everywhere else (see Mathematica code below). - John M. Campbell, Jun 23 2011
For n > 0: a(n) = Sum_{k=1..n-1} (A039913(n-1,k)) / 2. - Reinhard Zumkeller, Oct 07 2012
The right-hand side of a binomial-coefficient identity [Gauthier]. - N. J. A. Sloane, Apr 09 2013
a(n) is the number of edges in the Fibonacci cube Gamma(n-1) (see the Klavzar 2005 reference, p. 149). Example: a(3)=2; indeed, the Fibonacci cube Gamma(2) is the path P(3) having 2 edges. - Emeric Deutsch, Aug 10 2014
a(n) is the number of c(i)'s, including repetitions, in p(n), where p(n)/q(n) is the n-th convergent p(n)/q(n) of the formal infinite continued fraction [c(0), c(1), ...]; e.g., the number of c(i)'s in p(3) = c(0)*c(1)*c(2)*c(3) + c(0)*c(1) + c(0)*c(3) + c(2)*c(3) + 1 is a(5) = 10. - Clark Kimberling, Dec 23 2015
Also the number of maximal and maximum cliques in the (n-1)-Fibonacci cube graph. - Eric W. Weisstein, Sep 07 2017
a(n+1) is the total number of fixed points in all permutations p on 1, 2, ..., n such that |k-p(k)| <= 1 for 1 <= k <= n. - Katharine Ahrens, Sep 03 2019
From Steven Finch, Mar 22 2020: (Start)
a(n+1) is the total binary weight (cf. A000120) of all A000045(n+2) binary sequences of length n not containing any adjacent 1's.
The only three 2-bitstrings without adjacent 1's are 00, 01 and 10. The bitsums of these are 0, 1 and 1. Adding these give a(3)=2.
The only five 3-bitstrings without adjacent 1's are 000, 001, 010, 100 and 101. The bitsums of these are 0, 1, 1, 1 and 2. Adding these give a(4)=5.
The only eight 4-bitstrings without adjacent 1's are 0000, 0001, 0010, 0100, 1000, 0101, 1010 and 1001. The bitsums of these are 0, 1, 1, 1, 1, 2, 2, and 2. Adding these give a(5)=10. (End)
Number of tilings of a 1 X n strip with monominoes (1 X 1 squares) and at least one domino (1 X 2 rectangles), where exactly one of the dominoes is colored gold. - Greg Dresden and Jiachen Weng, Jul 31 2025

			G.f. = x^2 + 2*x^3 + 5*x^4 + 10*x^5 + 20*x^6 + 38*x^7 + 71*x^8 + 130*x^9 + ... - _Michael Somos_, Jun 24 2018

Donald E. Knuth, Fundamental Algorithms, Addison-Wesley, 1968, p. 83, Eq. 1.2.8--(17). - Don Knuth, Feb 26 2019
Thomas Koshy, Fibonacci and Lucas Numbers with Applications, 2001, Chapter 15, page 187, "Hosoya's Triangle", and p. 375, eq. (32.13).
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989, p. 183, Nr.(98).

T. D. Noe, Table of n, a(n) for n = 0..500
Marco Abrate, Stefano Barbero, Umberto Cerruti and Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", Discrete Math. 335 (2014), 1--7. MR3248794.
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
Carlos Alirio Rico Acevedo and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci, Hypercubes and Isometric Words based on Swap and Mismatch Distance, arXiv:2303.09898 [math.CO], 2023.
Kassie Archer and Robert P. Laudone, Pattern avoidance and the fundamental bijection, arXiv:2407.06338 [math.CO], 2024. See p. 6.
Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar and Marko Petkovšek, Vertex and edge orbits of Fibonacci and Lucas cubes, arXiv:1407.4962 [math.CO], 2014. See Table 2.
Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar, et al., Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings, 2014.
Jean-Luc Baril, Sergey Kirgizov and Vincent Vajnovszki, Gray codes for Fibonacci q-decreasing words, arXiv:2010.09505 [cs.DM], 2020.
Daniel Birmajer, Juan Gil and Michael D. Weiner, Linear recurrence sequences and their convolutions via Bell polynomials, arXiv:1405.7727 [math.CO], 2014.
Daniel Birmajer, Juan B. Gil and Michael D. Weiner, Linear Recurrence Sequences and Their Convolutions via Bell Polynomials, Journal of Integer Sequences, 18 (2015), #15.1.2.
Matthew Blair, Rigoberto Flórez and Antara Mukherjee, Matrices in the Hosoya triangle, arXiv:1808.05278 [math.CO], 2018.
Matthew Blair, Rigoberto Flórez and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 5.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Giuseppa Castiglione, Antonio Restivo and Marinella Sciortino, Circular Sturmian words and Hopcroft's algorithm, Theor. Comput. Sci. 410, No. 43, 4372-4381 (2009)
Charles H. Conley and Valentin Ovsienko, Shadows of rationals and irrationals: supersymmetric continued fractions and the super modular group, arXiv:2209.10426 [math-ph], 2022.
Éva Czabarka, Rigoberto Flórez and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
Eric S. Egge, Restricted 3412-Avoiding Involutions, p. 16, arXiv:math/0307050 [math.CO], 2003.
Sergio Falcon, Half self-convolution of the k-Fibonacci sequence, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 96-106.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
Rigoberto Flórez, Robinson Higuita and Alexander Ramírez, The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials, arXiv:1808.01264 [math.NT], 2018.
Napoleon Gauthier (Proposer), Problem H-703, Fib. Quart., 50 (2012), 379-381.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
Martin Griffiths, Digit Proportions in Zeckendorf Representations, Fibonacci Quart. 48 (2010), no. 2, 168-174.
Verner E. Hoggatt, Jr. and M. Bicknell-Johnson, Fibonacci convolution sequences, Fib. Quart., 15 (1977), 117-122.
Milan Janjić, Hessenberg Matrices and Integer Sequences, J. Int. Seq. 13 (2010) # 10.7.8, section 3.
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 8.
Sandi Klavžar, On median nature and enumerative properties of Fibonacci-like cubes, Disc. Math. 299 (2005), 145-153.
Sandi Klavžar, Structure of Fibonacci cubes: a survey, Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia; Preprint series Vol. 49 (2011), 1150 ISSN 2232-2094. (See Section 4.)
Toufik Mansour, Generalization of some identities involving the Fibonacci numbers, arXiv:math/0301157 [math.CO], 2003.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
Pieter Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.
Pieter Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
László Németh, Walks on tiled boards, arXiv:2403.12159 [math.CO], 2024. See p. 2.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Valentin Ovsienko, Shadow sequences of integers, from Fibonacci to Markov and back, arXiv:2111.02553 [math.CO], 2021.
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.
Mihai Prunescu and Lorenzo Sauras-Altuzarra, On the representation of C-recursive integer sequences by arithmetic terms, arXiv:2405.04083 [math.LO], 2024. See p. 18.
Jeffrey B. Remmel and J. L. B. Tiefenbruck, Q-analogues of convolutions of Fibonacci numbers, Australasian Journal of Combinatorics, Volume 64(1) (2016), Pages 166-193.
J. Riordan, Notes to N. J. A. Sloane, Jul. 1968
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Maximum Clique
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Row sums of triangles A058071, A134510, A134836.
First differences of A006478.
Cf. A000032, A000045, A001628, A010049, A037027, A055244, A214178.

List([0..40],n->Sum([0..n],k->Fibonacci(k)*Fibonacci(n-k))); # Muniru A Asiru, Jun 24 2018

a001629 n = a001629_list !! (n-1)
a001629_list = f [] $ tail a000045_list where
   f us (v:vs) = (sum $ zipWith (*) us a000045_list) : f (v:us) vs
-- Reinhard Zumkeller, Jan 18 2014, Oct 16 2011

I:=[0,0,1,2]; [n le 4 select I[n] else 2*Self(n-1)+Self(n-2)-2*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Nov 19 2014

a:= n-> (<<2|1|0|0>, <1|0|1|0>, <-2|0|0|1>, <-1|0|0|0>>^n)[1,3]:
seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008
# Alternative:
A001629 := n -> `if`(n<2, 0, (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4)):
seq(simplify(A001629(n)), n=0..37); # Peter Luschny, Apr 10 2018

Table[Sum[Binomial[n-i, i] i, {i, 0, n}], {n, 0, 34}] (* Geoffrey Critzer, May 04 2009 *)
Table[Abs[(1 -(1/2 -I/2)(1 - (-1)^n))*Coefficient[CharacteristicPolynomial[ Array[KroneckerDelta[#1, #2] I + KroneckerDelta[#1 + 1, #2] + KroneckerDelta[#1 -1, #2] &, {n-1, n-1}], x], x]], {n,2,50}] (* John M. Campbell, Jun 23 2011 *)
LinearRecurrence[{2,1,-2,-1}, {0,0,1,2}, 40] (* Harvey P. Dale, Aug 26 2013 *)
CoefficientList[Series[x^2/(1-x-x^2)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Nov 19 2014 *)
Table[(2nFibonacci[n-1] + (n-1)Fibonacci[n])/5, {n, 0, 40}] (* Vladimir Reshetnikov, May 08 2016 *)
Table[With[{fibs=Fibonacci[Range[n]]},ListConvolve[fibs,fibs]],{n,-1,40}]//Flatten (* Harvey P. Dale, Aug 19 2018 *)

Vec(1/(1-x-x^2)^2+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-2,1,2]^n)[2,4] \\ Charles R Greathouse IV, Jul 20 2016

def A001629(n): return (1/5)*(n*lucas_number2(n, 1, -1) - fibonacci(n))
[A001629(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

G.f.: x^2/(1 - x - x^2)^2. - Simon Plouffe in his 1992 dissertation
a(n) = A037027(n-1, 1), n >= 1 (Fibonacci convolution triangle).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), n > 3.
a(n) = Sum_{k=0..n} A000045(k)*A000045(n-k).
a(n+1) = Sum_{i=0..F(n)} A007895(i), where F = A000045, the Fibonacci sequence. - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 04 2001
a(n) = Sum_{k=0..floor(n/2)-1} (k+1)*binomial(n-k-1, k+1). - Emeric Deutsch, Nov 15 2001
a(n) = floor( (1/5)*(n - 1/sqrt(5))*phi^n + 1/2 ) where phi=(1+sqrt(5))/2 is the golden ratio. - Benoit Cloitre, Jan 05 2003
a(n) = a(n-1) + A010049(n-1) for n > 0. - Emeric Deutsch, Dec 10 2003
a(n) = Sum_{k=0..floor((n-2)/2)} (n-k-1)*binomial(n-k-2, k). - Paul Barry, Jan 25 2005
a(n) = ((n-1)*F(n) + 2*n*F(n-1))/5, F(n)=A000045(n) (see Vajda and Koshy reference).
F'(n, 1), the first derivative of the n-th Fibonacci polynomial evaluated at 1. - T. D. Noe, Jan 18 2006
a(n) = a(n-1) + a(n-2) + F(n-1), where F=A000045, the Fibonacci sequence. - Graeme McRae, Jun 02 2006
a(n) = (1/5)*(n-1/sqrt(5))*((1+sqrt(5))/2)^n + (1/5)*(n+1/sqrt(5))*((1-sqrt(5))/2)^n. - Graeme McRae, Jun 02 2006
a(n) = A055244(n-1) - F(n-2). Example: a(6) = 20 = A055244(5) - F(3) = (23 - 3). - Gary W. Adamson, Jul 27 2007
a(n) = term (1,3) in the 4 X 4 matrix [2,1,0,0; 1,0,1,0; -2,0,0,1; -1,0,0,0]^n. - Alois P. Heinz, Aug 01 2008
a(n) = A214178(n,1) for n > 0. - Reinhard Zumkeller, Jul 08 2012
a(n) = ((n+1)*F(n-1) + (n-1)*F(n+1))/5. - Richard R. Forberg, Aug 04 2014
(n-2)*a(n) - (n-1)*a(n-1) - n*a(n-2) = 0, n > 1. - Michael D. Weiner, Nov 18 2014
a(n) = Sum_{i=0..n-1} Sum_{j=0..i} F(j-1)*F(i-j), where F(n) = A000045 Fibonacci Numbers. - Carlos A. Rico A., Jul 14 2016
a(n) = (n*Lucas(n) - Fibonacci(n))/5, where Lucas = A000032, Fibonacci = A000045. - Vladimir Reshetnikov, Sep 27 2016
a(n) = (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4) for n >= 2. - Peter Luschny, Apr 10 2018
a(n) = -(-1)^n a(-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/50)*exp(-2*x/(1+sqrt(5)))*(2*sqrt(5)-5*(-1+sqrt(5))*x+exp(sqrt(5)*x)*(-2*sqrt(5)+5*(1+sqrt(5))*x)). - Stefano Spezia, Sep 03 2019
From Peter Bala, Jan 14 2025: (Start)
a(2*n+1) is even and a(2*n) has the same parity as Fibonacci(n).
For n >= 1, a(n) = (2/n)*Sum_{k = 0..n} k*Fibonacci(k)*Fibonacci(n-k). (End)

A002940 Arrays of dumbbells.

Original entry on oeis.org

1, 4, 11, 26, 56, 114, 223, 424, 789, 1444, 2608, 4660, 8253, 14508, 25343, 44030, 76136, 131110, 224955, 384720, 656041, 1115784, 1893216, 3205416, 5416441, 9136084, 15384563, 25866914, 43429784, 72821274, 121953943, 204002680, 340886973, 569047468, 949022608

Offset: 1

N. J. A. Sloane

Whitney transform of n. The Whitney transform maps the sequence with g.f. g(x) to that with g.f. (1/(1-x))g(x(1+x)). - Paul Barry, Feb 16 2005
a(n-1) is the permanent of the n X n 0-1 matrix with 1 in (i,j) position iff (i=1 and j1). For example, with n=5, a(4) = per([[1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 0, 1, 1, 1]]) = 26. - David Callan, Jun 07 2006
a(n) is the internal path length of the Fibonacci tree of order n+2. 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. The internal path length of a tree is the sum of the levels of all of its internal (i.e. non-leaf) nodes. - Emeric Deutsch, Jun 15 2010
Partial Sums of A023610 - John Molokach, Jul 03 2013

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(2.3.14).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Carlos Alirio Rico Acevedo and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See pp. 23-24.
R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.
R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15.2 (1974), 214-216. (Annotated scanned copy)
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 x N arrays of dumbbells, J. Math. Phys., 11 (1970), 3095-3099.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

Cf. A002941, A002889, A055608, A062123, A062124, A062125, A062126, A062127, A046741.

Cf. A000045, A001925, A023610, A054454, A006478, A067331, A178523.

a002940 n = a002940_list !! (n-1)
a002940_list = 1 : 4 : 11 : zipWith (+)
   (zipWith (-) (map (* 2) $ drop 2 a002940_list) a002940_list)
   (drop 5 a000045_list)
-- Reinhard Zumkeller, Jan 18 2014

m:=35; R:=PowerSeriesRing(Integers(), m); Coefficients(R!( (1+x)/((1-x)*(1-x-x^2)^2) )); // G. C. Greubel, Jan 31 2019

a[n_]:= a[n]= If[n<3, n^2, 2a[n-1] -a[n-3] +Fibonacci[n+1]]; Array[a, 32] (* Jean-François Alcover, Jul 31 2018 *)

my(x='x+O('x^35)); Vec((1+x)/((1-x)*(1-x-x^2)^2)) \\ G. C. Greubel, Jan 31 2019

((1+x)/((1-x)*(1-x-x^2)^2)).series(x, 35).coefficients(x, sparse=False) # G. C. Greubel, Jan 31 2019

a(n) = 2*a(n-1) - a(n-3) + A000045(n+1).
G.f.: x*(1+x)/((1-x)*(1-x-x^2)^2).
a(n) = Sum_{k=0..n} ( Sum_{i=0..n} k*C(k, i-k) ). - Paul Barry, Feb 16 2005
E.g.f.: 2*exp(x) + exp(x/2)*((55*x - 50)*cosh(sqrt(5)*x/2) + sqrt(5)*(25*x - 22)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 03 2023

More terms from Henry Bottomley, Jun 02 2000

A178523 The path length of the Fibonacci tree of order n.

Original entry on oeis.org

0, 0, 2, 6, 16, 36, 76, 152, 294, 554, 1024, 1864, 3352, 5968, 10538, 18478, 32208, 55852, 96420, 165800, 284110, 485330, 826752, 1404816, 2381616, 4029216, 6803666, 11468502, 19300624, 32433204, 54426364, 91216184, 152691702, 255313658, 426460288, 711634648

Offset: 0

Emeric Deutsch, Jun 15 2010

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. The path length of a tree is the sum of the levels of all of its nodes.

This is also the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that all but one such pair are joined by an edge; equivalently the number of "(n-1)-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - Donovan Young, Oct 23 2018

			a(2)=2 because the Fibonacci tree of order 2 is /\ with path length 1 + 1. - _Emeric Deutsch_, Sep 13 2010

Ralph P. Grimaldi, Properties of Fibonacci trees, In Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991); Congressus Numerantium 84 (1991), 21-32. - Emeric Deutsch, Sep 13 2010
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Muniru A Asiru, Table of n, a(n) for n = 0..4500
Carlos Alirio Rico Acevedo, and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 2015-2017.
D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

Cf. A000045, A006478, A178522, A002940, A067331.

a:=[0,2];;  for n in [3..35] do a[n]:=a[n-1]+a[n-2]+ 2*Fibonacci(n +1) -2; od; Concatenation([0],a); # Muniru A Asiru, Oct 23 2018

[2+(2/5)*(4*n-9)*Fibonacci(n)+(2/5)*(3*n-5)*Fibonacci(n-1): n in [0..40]]; // Vincenzo Librandi, Oct 24 2018

with(combinat): a := proc (n) options operator, arrow: 2+((8/5)*n-18/5)*fibonacci(n)+((6/5)*n-2)*fibonacci(n-1) end proc: seq(a(n), n = 0 .. 35);
G := 2*z^2/((1-z)*(1-z-z^2)^2): Gser := series(G, z = 0, 40): seq(coeff(Gser, z, n), n = 0 .. 35);

Table[2 +2/5 (4n-9) Fibonacci[n] +2/5 (3n -5) Fibonacci[n-1], {n, 0, 40}] (* or *) LinearRecurrence[{3, -1, -3, 1, 1}, {0, 0, 2, 6, 16}, 40] (* Harvey P. Dale, Oct 02 2016 *)

vector(40, n, n--; (10+(8*n-18)*fibonacci(n)+(6*n-10)*fibonacci(n-1))/5) \\ G. C. Greubel, Jan 31 2019

[(10+(8*n-18)*fibonacci(n)+(6*n-10)*fibonacci(n-1))/5 for n in range(40)] # G. C. Greubel, Jan 31 2019

a(n) = 2 + (2/5)*(4n-9)*F(n) + (2/5)*(3n-5)*F(n-1), where F(n) = A000045(n) (Fibonacci numbers).
a(n) = 2*A006478(n+1).
a(n) = Sum_{k=0..n-1} k*A178522(n,k).
G.f.: 2*z^2/((1-z)*(1-z-z^2)^2).
From Emeric Deutsch, Sep 13 2010: (Start)
a(0)=a(1)=0, a(n) = a(n-1)+a(n-2)+2F(n+1)-2 if n>=2; here F(j)=A000045(j) are the Fibonacci numbers (see the Grimaldi reference, Eq. (**) on p. 23).
An explicit formula for a(n) is given in the Grimaldi reference (Theorem 2).
(End)
E.g.f.: 2*exp(x) + 2*exp(x/2)*(5*(4*x - 5)*cosh(sqrt(5)*x/2) + sqrt(5)*(10*x - 13)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 04 2023

A122491 a(n) = n * Fibonacci(n) - Sum_{i=0..n} Fibonacci(i).

Original entry on oeis.org

0, 0, 0, 2, 5, 13, 28, 58, 114, 218, 407, 747, 1352, 2420, 4292, 7554, 13209, 22969, 39748, 68494, 117590, 201210, 343275, 584087, 991440, 1679208, 2838408, 4789058, 8066669, 13566373, 22782892, 38209762, 64003002, 107083610, 178967807, 298803459, 498404504

Offset: 0

Ben Paul Thurston, Sep 16 2006

Similar to A190062.

Also the circuit rank and corank of the n-Lucas cube graph. - Eric W. Weisstein, Jul 28 2023

			a(5) = 13 because Fib(5) = 5, times 5 = 25 and subtract sum(Fib(5)) = 12 to get 13.

Bruno Berselli, Table of n, a(n) for n = 0..1000
Carlos Alirio Rico Acevedo, Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
Eric Weisstein's World of Mathematics, Circuit Rank
Eric Weisstein's World of Mathematics, Corank
Eric Weisstein's World of Mathematics, Lucas Cube Graph
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

Cf. A000045.

with(combinat, fibonacci): for i from 1 to 30 do i*fibonacci(i) - sum(fibonacci(k), k=0..i); end do;

Table[n Fibonacci[n] - Fibonacci[n + 2] + 1, {n, 0, 40}] (* Stefan Steinerberger, Feb 22 2008 *)
LinearRecurrence[{3, -1, -3, 1, 1}, {0, 0, 0, 2, 5}, 40] (* Harvey P. Dale, May 17 2016 *)

a(n)=n*fibonacci(n) - fibonacci(n+2) + 1 \\ Charles R Greathouse IV, Oct 07 2015

a(n) = n * Fibonacci(n) - Fibonacci(n+2) + 1. - Stefan Steinerberger, Feb 22 2008
G.f.: x^3*(2-x)/((1-x)*(1-x-x^2)^2). - Colin Barker, Feb 10 2012
a(n+2) = Sum_{k=0..n} A099920(k). - J. M. Bergot, Apr 13 2013
a(n) = 2*A006478(n)-A006478(n-1). - R. J. Mathar, May 04 2014

Edited by N. J. A. Sloane, Sep 17 2006

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

Original entry on oeis.org

1, -1, 4, -6, 14, -24, 47, -83, 152, -268, 476, -832, 1453, -2517, 4348, -7474, 12810, -21880, 37275, -63335, 107376, -181656, 306744, -517056, 870169, -1462249, 2453812, -4112478, 6884102, -11510808, 19226951, -32084027, 53489288, -89097892, 148290068

Offset: 0

Roger L. Bagula, Dec 04 2010

			G.f. = 1 - x + 4*x^2 - 6*x^3 + 14*x^4 - 24*x^5 + 47*x^6 - 83*x^7 + 152*x^8 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (-1,3,1,-3,1).

Cf. m=1: A077899, m large: A077925.

Cf. A000032, A000045, A006478.

List([0..40], n-> 1 + (-1)^n*(n*Lucas(1,-1,n+1)[2] + 7*Fibonacci(n))/5 ); # G. C. Greubel, Dec 04 2019

m:=50; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1/((1-x)*(1+x-x^2)^2))); // G. C. Greubel, Aug 14 2018

with(combinat); seq( 1 + (-1)^n*(n*fibonacci(n+2) + (n+7)*fibonacci(n))/5, n=0..40); # G. C. Greubel, Dec 04 2019

f[x_, m_] = ExpandAll[(x -x^(m+1))*(1-x-x^2) -(1 -2*x +x^(m+1))];
g[x_, n_] = ExpandAll[x^(m + 3)*f[1/x, m]];
a = Table[Table[SeriesCoefficient[Series[1/g[x, m], {x, 0, 20}], n], {n, 0, 20}], {m, 1, 20}]
CoefficientList[Series[1/((1-x)(1+x-x^2)^2), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 13 2014 *)
RecurrenceTable[{a[0]==1,a[1]==-1,a[n]==-a[n-1]+a[n-2]-Fibonacci[-n]+1},a,{n,40}] (* Harvey P. Dale, May 12 2018 *)
Table[1 + (-1)^n*(n*LucasL[n+1] + 7*Fibonacci[n])/5, {n,0,40}] (* G. C. Greubel, Dec 04 2019 *)

{a(n) = if( n<0, polcoeff( x^5 / ((1 - x) * (1 - x - x^2)^2) + x * O(x^-n), -n), polcoeff( 1 / ((1 - x) * (1 + x - x^2)^2) + x * O(x^n), n))}; /* Michael Somos, Mar 11 2014 */

vector(41, n, my(f=fibonacci); 1 -(-1)^n*((n-1)*f(n+1) +(n+6)*f(n-1))/5 ) \\ G. C. Greubel, Dec 04 2019

[1 + (-1)^n*(n*lucas_number2(n+1, 1,-1) + 7*fibonacci(n))/5 for n in (0..40)] # G. C. Greubel, Dec 04 2019

G.f.: 1/(- x^m + 1 - x^(1 + m) + x + 3*x^(2 + m) - 2*x^2 - x^(3 + m)) for m=2.
G.f.: 1 / ((1 - x) * (1 + x - x^2)^2). - Michael Somos, Mar 11 2014
a(n) = A006478(-2-n) for all n in Z. - Michael Somos, Mar 11 2014
a(n) = 1 + (-1)^n*(n*Lucas(n+1) + 7*Fibonacci(n))/5. - G. C. Greubel, Dec 04 2019
E.g.f.: exp(-x/2)*(25*exp(3*x/2) - 15*x*cosh(sqrt(5)*x/2) + sqrt(5)*(5*x - 14)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Jul 24 2022

cp's OEIS Frontend

A001629 Self-convolution of Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A002940 Arrays of dumbbells.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Sage

Formula

Extensions

A178523 The path length of the Fibonacci tree of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A122491 a(n) = n * Fibonacci(n) - Sum_{i=0..n} Fibonacci(i).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI