A001628 - OEIS

%I M2789 N1124 #150 Jan 05 2025 19:51:32

%S 1,3,9,22,51,111,233,474,942,1836,3522,6666,12473,23109,42447,77378,

%T 140109,252177,451441,804228,1426380,2519640,4434420,7777860,13599505,

%U 23709783,41225349,71501422,123723351,213619683,368080793,633011454,1086665562,1862264196

%N Convolved Fibonacci numbers.

%C a(n-2) = (((-i)^(n-2))/2)*(d^2/dx^2)S(n,x)|_{x=i}, n>=2. Second derivative of Chebyshev S-polynomials evaluated at x=i (imaginary unit) multiplied by ((-i)^(n-2))/2. See A049310 for the S-polynomials. - _Wolfdieter Lang_, Apr 04 2007

%C a(n) = number of weak compositions of n in which exactly 2 parts are 0 and all other parts are either 1 or 2. - _Milan Janjic_, Jun 28 2010

%C Number of 4-cycles in the Fibonacci cube Gamma[n+3] (see the Klavzar reference, p. 511). - _Emeric Deutsch_, Apr 17 2014

%D T. Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001, p. 375.

%D J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H G. C. Greubel, <a href="/A001628/b001628.txt">Table of n, a(n) for n = 0..4500</a> (terms 0..500 from T. D. Noe)

%H Daniel Birmajer, Juan Gil, and Michael D. Weiner, <a href="http://arxiv.org/abs/1405.7727">Linear recurrence sequences and their convolutions via Bell polynomials</a>, arXiv:1405.7727 [math.CO], 2014.

%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Gil/gil3.html">Linear Recurrence Sequences and Their Convolutions via Bell Polynomials</a>, Journal of Integer Sequences, 18 (2015), #15.1.2.

%H Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Verner E. Hoggatt, Jr., <a href="/A001628/a001628.pdf">Letters to N. J. A. Sloane, 1974-1975</a>

%H Verner E. Hoggatt, Jr. and Marjorie Bicknell-Johnson, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/15-2/hoggatt1.pdf">Fibonacci convolution sequences</a>, Fib. Quart., 15 (1977), 117-122.

%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Janjic/janjic33.html">Hessenberg Matrices and Integer Sequences </a>, J. Int. Seq. 13 (2010) # 10.7.8, section 3.

%H Sandi Klavžar, <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/FibonacciCubesRevised.pdf">Structure of Fibonacci cubes: a survey</a>, preprint.

%H Sandi Klavžar, <a href="https://doi.org/10.1007/s10878-011-9433-z">Structure of Fibonacci cubes: a survey</a>, J. Comb. Optim., 25, 2013, 505-522

%H Toufik Mansour, <a href="http://arXiv.org/abs/math.CO/0301157">Generalization of some identities involving the Fibonacci numbers</a>, arXiv:math/0301157 [math.CO], 2003.

%H Pieter Moree, <a href="http://arXiv.org/abs/math.CO/0311205">Convoluted convolved Fibonacci numbers</a>, arXiv:math/0311205 [math.CO], 2003.

%H Pieter Moree, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Moree/moree12.htm">Convoluted Convolved Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.

%H Mihai Prunescu and Lorenzo Sauras-Altuzarra, <a href="https://arxiv.org/abs/2405.04083">On the representation of C-recursive integer sequences by arithmetic terms</a>, arXiv:2405.04083 [math.LO], 2024. See p. 18.

%H Jeffrey B. Remmel and J. L. B. Tiefenbruck, <a href="https://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p166.pdf">Q-analogues of convolutions of Fibonacci numbers</a>, Australasian Journal of Combinatorics, Volume 64(1) (2016), Pages 166-193.

%H John Riordan, <a href="/A000262/a000262_1.pdf">Letter to N. J. A. Sloane, Oct. 1970</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciCubeGraph.html">Fibonacci Cube Graph</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-5,0,3,1).

%F G.f.: 1 / (1 - x - x^2)^3.

%F a(n) = A037027(n+2,2) (Fibonacci convolution triangle).

%F a(n) = ((5*n+16)*(n+1)*F(n+2)+(5*n+17)*(n+2)*F(n+1))/50, F=A000045. - _Wolfdieter Lang_, Apr 12 2000 (This formula coincides with eq. (32.14) of the Koshy reference, p. 375, if there n -> n+3. - _Wolfdieter Lang_, Aug 03 2012)

%F For n>2, a(n-2) = sum(i+j+k=n, F(i)*F(j)*F(k)). - _Benoit Cloitre_, Nov 01 2002

%F a(n) = F''(n+2, 1)/2, i.e. 1/2 times the 2nd derivative of the (n+2)th Fibonacci polynomial evaluated at 1. - _T. D. Noe_, Jan 18 2006

%F a(n) = Sum_{k=0..n} C(k,n-k)*C(k+2,2). - _Paul Barry_, Apr 13 2008

%F 0 = n*a(n) - (n+2)*a(n-1) - (n+4)*a(n-2), n>1. - _Michael D. Weiner_, Nov 18 2014

%F a(n) = 3*a(n-1) - 5*a(n-3) + 3*a(n-5) + a(n-6). - _Eric W. Weisstein_, Sep 05 2017

%e G.f. = 1 + 3*x + 9*x^2 + 22*x^3 + 51*x^4 + 111*x^5 + 233*x^6 + 474*x^7 + ...

%p A001628:=-1/(z**2+z-1)**3; [_Simon Plouffe_ in his 1992 dissertation.]

%p a:= n-> (Matrix(6, (i, j)-> `if` (i=j-1, 1, `if` (j=1, [3, 0, -5, 0, 3, 1][i], 0)))^n)[1,1]: seq (a(n), n=0..29); # _Alois P. Heinz_, Aug 01 2008

%t CoefficientList[Series[1/(-z^2 - z + 1)^3, {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jul 01 2011 *)

%t (* Start _Eric W. Weisstein_, Sep 05 2017 *)

%t Table[Derivative[2][Fibonacci[n + 2, #] &][1]/2, {n, 20}]

%t Derivative[2][Fibonacci[Range[20] + 2, #] &][1]/2

%t LinearRecurrence[{3, 0, -5, 0, 3, 1}, {1, 3, 9, 22, 51, 111}, 20]

%t Table[-I^(n + 1) Derivative[2][ChebyshevU[n + 1, -#/2] &][I]/2, {n, 20}]

%t (* End *)

%o (PARI) Vec((1 - x - x^2 )^-3+O(x^99)) \\ _Charles R Greathouse IV_, Jul 01 2011

%o (Magma) [(&+[Binomial(k,n-k)*Binomial(k+2,2): k in [0..n]]): n in [0..30]]; // _G. C. Greubel_, Jan 10 2018

%Y a(n) = A037027(n+2,2) (Fibonacci convolution triangle).

%Y Cf. A055243 (first differences).

%Y Cf. A291915 (6-cycles).

%K nonn,easy,changed

%O 0,2

%A _N. J. A. Sloane_, _Simon Plouffe_