|
|
A004798
|
|
Convolution of Fibonacci numbers 1,2,3,5,... with themselves.
|
|
13
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
|
|
|
FORMULA
|
O.g.f.: (x+1)^2*x/(1-x-x^2)^2. - Len Smiley, Dec 11 2001
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) = Sum_{i=0..floor((n+1)/2)} binomial(n+1-i,i)*(n-i). - John M. Campbell, Apr 07 2018
a(n) = n*(hypergeom([-(n+1)/2, -n/2], [-n - 1], -4) - hypergeom([(1-n)/2, 1 - n/2], [-n], -4)).
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|