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,2

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

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

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

Example

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

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

Prog

(PARI) Vec(((1+x)/(1-x-x^2))^2+O(x^66)) \\ Joerg Arndt, Jul 04 2013
(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
(Sage) [(n*lucas_number2(n+3, 1, -1) - 2*fibonacci(n))/5 for n in (1..40)] # G. C. Greubel, Jul 07 2019
(GAP) List([1..40], n-> (n*Lucas(1, -1, n+3)[2] - 2*Fibonacci(n))/5); # G. C. Greubel, Jul 07 2019

Crossrefs

Cf. A171855, A000045.

Cf. A000032, A001629, A030528, A045925.

Sequence in context: A294683 A265051 A266375 * A265052 A266372 A174622

Adjacent sequences: A004795 A004796 A004797 * A004799 A004800 A004801

Keyword

nonn,easy

Author

Clark Kimberling

Status

approved