cp's OEIS Frontend

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

%I A004798 #65 Jan 07 2025 16:51:01
%S A004798 1,4,10,22,45,88,167,310,566,1020,1819,3216,5645,9848,17090,29522,
%T A004798 50793,87080,148819,253610,431086,731064,1237175,2089632,3523225,
%U A004798 5930668,9968122,16730830,28045221,46954360,78524159,131181406,218933030,365044788,608135635,1012268592
%N A004798 Convolution of Fibonacci numbers 1,2,3,5,... with themselves.
%C A004798 From _Emeric Deutsch_, Feb 15 2010: (Start)
%C A004798 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.
%C A004798 a(n) = Sum_{k>=0} k*A171855(n + 3,k). (End)
%C A004798 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
%H A004798 Vincenzo Librandi, <a href="/A004798/b004798.txt">Table of n, a(n) for n = 1..1000</a>
%H A004798 É. Czabarka, R. Flórez, and L. Junes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Florez/florez12.html">A Discrete Convolution on the Generalized Hosoya Triangle</a>, Journal of Integer Sequences, 18 (2015), #15.1.6.
%H A004798 Bridget Eileen Tenner, <a href="https://arxiv.org/abs/2001.05011">Interval structures in the Bruhat and weak orders</a>, arXiv:2001.05011 [math.CO], 2020.
%H A004798 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).
%F A004798 O.g.f.: (x+1)^2*x/(1-x-x^2)^2. - _Len Smiley_, Dec 11 2001
%F A004798 a(n) = a(n-1) + a(n-2) + Fibonacci(n+2). - _Philippe Deléham_, Jan 22 2012
%F A004798 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
%F A004798 a(n) = A001629(n+1) + A001629(n-1) + 2*A001629(n). - _R. J. Mathar_, Oct 30 2015
%F A004798 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
%F A004798 a(n) = Sum_{i=0..floor((n+1)/2)} binomial(n+1-i,i)*(n-i). - _John M. Campbell_, Apr 07 2018
%F A004798 From _Peter Luschny_, Apr 10 2018: (Start)
%F A004798 a(n) = n*(hypergeom([-(n+1)/2, -n/2], [-n - 1], -4) - hypergeom([(1-n)/2, 1 - n/2], [-n], -4)).
%F A004798 a(n) = n*A000045(n+2) - A001629(n+1). (End)
%F A004798 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
%e A004798 a(6) = 45 + 22 + A000045(6+2) = 45 + 22 + 21 = 88. - _Philippe Deléham_, Jan 22 2012
%p A004798 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]:
%p A004798 seq(a(n), n=1..40);  # _Alois P. Heinz_, Jul 04 2013
%p A004798 # Alternative:
%p A004798 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
%t A004798 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 *)
%t A004798 Table[n Fibonacci[n] + 2/5 (n LucasL[n] - Fibonacci[n]), {n, 40}] (* _Vladimir Reshetnikov_, Sep 27 2016 *)
%t A004798 a[n_] := ListConvolve[f = Fibonacci[Range[2, n+1]], f][[1]]; Array[a, 40] (* _Jean-François Alcover_, Feb 15 2018 *)
%t A004798 LinearRecurrence[{2, 1, -2, -1}, {1, 4, 10, 22}, 40] (* _Vincenzo Librandi_, Apr 08 2014 *)
%o A004798 (PARI) Vec(((1+x)/(1-x-x^2))^2+O(x^66)) \\ _Joerg Arndt_, Jul 04 2013
%o A004798 (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
%o A004798 (Sage) [(n*lucas_number2(n+3,1,-1) - 2*fibonacci(n))/5 for n in (1..40)] # _G. C. Greubel_, Jul 07 2019
%o A004798 (GAP) List([1..40], n-> (n*Lucas(1,-1,n+3)[2] - 2*Fibonacci(n))/5); # _G. C. Greubel_, Jul 07 2019
%Y A004798 Cf. A171855, A000045.
%Y A004798 Cf. A000032, A001629, A030528, A045925.
%K A004798 nonn,easy
%O A004798 1,2
%A A004798 _Clark Kimberling_