A001872 Convolved Fibonacci numbers.

1, 4, 14, 40, 105, 256, 594, 1324, 2860, 6020, 12402, 25088, 49963, 98160, 190570, 366108, 696787, 1315072, 2463300, 4582600, 8472280, 15574520, 28481220, 51833600, 93914325, 169457708, 304597382, 545556512, 973877245, 1733053440, 3075011478

Offset: 0

Author

N. J. A. Sloane and Simon Plouffe

Keywords

• nonn
• easy

Comments

6*a(n) is the number of ways to tile a strip of length n+6 with squares and three colors of dominos, where we must have the same number of dominos of each color. - Greg Dresden and Jiachen Weng, Aug 14 2025

References

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

Links

• T. D. Noe, Table of n, a(n) for n = 0..500
• 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 Gil and Michael D. Weiner, Linear Recurrence Sequences and Their Convolutions via Bell Polynomials, Journal of Integer Sequences, 18 (2015), #15.1.2.
• Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
• Verner E. Hoggatt, Jr. and Marjorie 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.
• Toufik Mansour, Generalization of some identities involving the Fibonacci numbers, arXiv:math/0301157 [math.CO], 2003.
• Pieter Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.
• 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.
• Index entries for linear recurrences with constant coefficients, signature (4,-2,-8,5,8,-2,-4,-1).

Programs

Magma

[(n+5)*(n+3)*(4*(n+1)*Fibonacci(n+2)+3*(n+2)*Fibonacci(n+1))/150: n in [0..30]]; // Vincenzo Librandi, Nov 19 2014

Maple

a := n-> (Matrix(8, (i,j)-> if (i=j-1) then 1 elif j=1 then [4,-2,-8,5, 8,-2,-4,-1][i] else 0 fi)^n)[1,1]; seq (a(n), n=0..29);  # Alois P. Heinz, Aug 15 2008

Mathematica

CoefficientList[Series[1/(1 - x - x^2)^4, {x, 0, 100}], x] (* Stefan Steinerberger, Apr 15 2006 *)

PARI

Vec( 1/(1 - x - x^2)^4 + O(x^66) )  \\ Joerg Arndt, May 12 2014

Formula

G.f.: 1/(1 - x - x^2)^4.

a(n) = A037027(n+3, 3) (Fibonacci convolution triangle).

a(n) = (n+5)*(n+3)*(4*(n+1)*F(n+2)+3*(n+2)*F(n+1))/150, F(n)=A000045(n). - Wolfdieter Lang, Apr 12 2000

For n > 3, a(n-3) = Sum_{h+i+j+k=n} F(h)*F(i)*F(j)*F(k). - Benoit Cloitre, Nov 01 2002

a(n) = F'''(n+3, 1)/6, i.e., 1/6 times the 3rd derivative of the (n+3)th Fibonacci polynomial evaluated at 1. - T. D. Noe, Jan 18 2006

a(n) = (((-i)^n)/3!)*(d^3/dx^3)S(n+3,x)|A049310%20for%20the%20S-polynomials.%20-%20_Wolfdieter%20Lang">{x=i}, where i is the imaginary unit. Third derivative of Chebyshev S(n+3,x) polynomial evaluated at x=i multiplied by ((-i)^(n-3))/3!. See A049310 for the S-polynomials. - _Wolfdieter Lang, Apr 04 2007

a(n) = Sum_{i=ceiling(n/2)..n} (i+1)*(i+2)*(i+3)*binomial(i,n-i)/6. - Vladimir Kruchinin, Apr 26 2011

Recurrence: a(n) = 4*a(n-1) - 2*a(n-2) - 8*a(n-3) + 5*a(n-4) + 8*a(n-5) - 2*a(n-6) - 4*a(n-7) - a(n-8). - Fung Lam, May 11 2014

n*a(n) - (n+3)*a(n-1) - (n+6)*a(n-2) = 0, n > 1. - Michael D. Weiner, Nov 18 2014