login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004798 Convolution of Fibonacci numbers 1,2,3,5,... with themselves. 11
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

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

a(n) = n*(hypergeom([-(n+1)/2, -n/2], [-n - 1], -4) - hypergeom([(1-n)/2, 1 - n/2], [-n], -4)). - Peter Luschny, Apr 10 2018

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. - Emeric Deutsch, Feb 15 2010

Cf. A001629. - Alois P. Heinz, Jul 04 2013

a(n) = n*A000045(n+2) - A001629(n+1). - Peter Luschny, Apr 10 2018

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 03:52 EST 2021. Contains 340384 sequences. (Running on oeis4.)