A004798 Convolution of Fibonacci numbers 1,2,3,5,... with themselves.

1, 4, 10, 22, 45, 88, 167, 310, 566, 1020, 1819, 3216, 5645, 9848, 17090, 29522, 50793, 87080, 148819, 253610, 431086, 731064, 1237175, 2089632, 3523225, 5930668, 9968122, 16730830, 28045221, 46954360, 78524159, 131181406, 218933030, 365044788, 608135635, 1012268592

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

From Emeric Deutsch, Feb 15 2010: (Start)

a(n) is the number of subwords of the form 0000 in all binary words of length n+3 that have no pair of adjacent 1's. Example: a(2)=4 because in the 13 (=A000045(7)) binary words of length 5 that have no pair of adjacent 1's, namely 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101, we have 2 + 1 + 0 + 0 + 0 + 0 + 0 + 0 + 1 + 1 + 0 + 0 + 0 = 4 subwords of the form 0000.

a(n) = Sum_{k>=0} k*A171855(n + 3,k). (End)

a(n) is the total number of 0's in all binary words of length n that have no pair of adjacent 1's. Example: a(5) = 45 because in the binary words listed in the above example there are respectively 5 + 4 + 4 + 4 + 3 + 4 + 3 + 3 + 4 + 3 + 3 + 3 + 2 = 45. - Geoffrey Critzer, Jul 22 2013

Examples

			a(6) = 45 + 22 + A000045(6+2) = 45 + 22 + 21 = 88. - _Philippe Deléham_, Jan 22 2012
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• É. Czabarka, R. Flórez, and L. Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
• Bridget Eileen Tenner, Interval structures in the Bruhat and weak orders, arXiv:2001.05011 [math.CO], 2020.
• Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Crossrefs

Cf. A171855, A000045.

Cf. A000032, A001629, A030528, A045925.

Programs

GAP

List([1..40], n-> (n*Lucas(1,-1,n+3)[2] - 2*Fibonacci(n))/5); # G. C. Greubel, Jul 07 2019

Magma

I:=[1,4,10,22]; [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, Apr 08 2018

Maple

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|-2|1|2>>^n. <<0, 1, 4, 10>>)[1, 1]:
seq(a(n), n=1..40);  # Alois P. Heinz, Jul 04 2013
# Alternative:
a := n -> n*(hypergeom([-(n+1)/2,-n/2],[-n-1],-4) - hypergeom([(1-n)/2,1-n/2],[-n], -4)): seq(simplify(a(n)), n=1..40); # Peter Luschny, Apr 10 2018

Mathematica

nn=40; Drop[CoefficientList[Series[D[(1+x)/(1-y x -y x^2),y]/.y->1,{x,0,nn}],x],1] (* Geoffrey Critzer, Jul 22 2013 *)
Table[n Fibonacci[n] + 2/5 (n LucasL[n] - Fibonacci[n]), {n, 40}] (* Vladimir Reshetnikov, Sep 27 2016 *)
a[n_] := ListConvolve[f = Fibonacci[Range[2, n+1]], f][[1]]; Array[a, 40] (* Jean-François Alcover, Feb 15 2018 *)
LinearRecurrence[{2, 1, -2, -1}, {1, 4, 10, 22}, 40] (* Vincenzo Librandi, Apr 08 2014 *)

PARI

Vec(((1+x)/(1-x-x^2))^2+O(x^66)) \\ Joerg Arndt, Jul 04 2013

Sage

[(n*lucas_number2(n+3,1,-1) - 2*fibonacci(n))/5 for n in (1..40)] # G. C. Greubel, Jul 07 2019

Formula

O.g.f.: (x+1)^2*x/(1-x-x^2)^2. - Len Smiley, Dec 11 2001

a(n) = a(n-1) + a(n-2) + Fibonacci(n+2). - Philippe Deléham, Jan 22 2012

O.g.f. is the derivative of A(x,y) with respect to y and then evaluated at y = 1, where A(x,y) is the o.g.f. for A030528. - Geoffrey Critzer, Jul 22 2013

a(n) = A001629(n+1) + A001629(n-1) + 2*A001629(n). - R. J. Mathar, Oct 30 2015

a(n) = n*Fibonacci(n) + (2/5)*(n*Lucas(n) - Fibonacci(n)) = A045925(n) + 2*A001629(n), where Lucas = A000032, Fibonacci = A000045. - Vladimir Reshetnikov, Sep 27 2016

a(n) = Sum_{i=0..floor((n+1)/2)} binomial(n+1-i,i)*(n-i). - John M. Campbell, Apr 07 2018

From Peter Luschny, Apr 10 2018: (Start)

a(n) = n*(hypergeom([-(n+1)/2, -n/2], [-n - 1], -4) - hypergeom([(1-n)/2, 1 - n/2], [-n], -4)).

a(n) = n*A000045(n+2) - A001629(n+1). (End)

E.g.f.: exp(x/2)*(35*x*cosh(sqrt(5)*x/2) + sqrt(5)*(15*x - 4)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 04 2023