%I #121 Mar 28 2024 10:53:26
%S 0,1,1,3,5,10,18,33,59,105,185,324,564,977,1685,2895,4957,8462,14406,
%T 24465,41455,70101,118321,199368,335400,563425,945193,1583643,2650229,
%U 4430290,7398330,12342849,20573219,34262337,57013865,94800780,157517532,261545777
%N Second-order Fibonacci numbers.
%C Number of parts in all compositions of n+1 with no 1's. E.g. a(5)=10 because in the compositions of 6 with no part equal to 1, namely 6,4+2,3+3,2+4,2+2+2, the total number of parts is 10. - _Emeric Deutsch_, Dec 10 2003
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 83.
%D Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin, Vol. 29 (1952), pp. 190-195.
%H Vincenzo Librandi, <a href="/A010049/b010049.txt">Table of n, a(n) for n = 0..1000</a>
%H Carlos A. Rico A. and Ana Paula Chaves, <a href="https://arxiv.org/abs/1903.07490">Double-Recurrence Fibonacci Numbers and Generalizations</a>, arXiv:1903.07490 [math.NT], 2019.
%H T. Amdeberhan and M. B. Can, M. Jensen, <a href="http://arxiv.org/abs/1406.0432">Divisors and specializations of Lucas polynomials</a>, arXiv preprint arXiv:1406.0432 [math.CO], 2014.
%H Kálmán Liptai, László Németh, Tamás Szakács, and László Szalay, <a href="https://arxiv.org/abs/2403.15053">On certain Fibonacci representations</a>, arXiv:2403.15053 [math.NT], 2024. See p. 2.
%H Mengmeng Liu and Andrew Yezhou Wang, <a href="https://www.emis.de/journals/JIS/VOL23/Wang/wang61.html">The Number of Designated Parts in Compositions with Restricted Parts</a>, J. Int. Seq., Vol. 23 (2020), Article 20.1.8.
%H Jia Huang, <a href="https://arxiv.org/abs/1812.11010">Compositions with restricted parts</a>, arXiv:1812.11010 [math.CO], 2018.
%H Loïc Turban, <a href="http://arxiv.org/abs/cond-mat/0011038">Lattice animals on a staircase and Fibonacci numbers</a>, arXiv:cond-mat/0011038 [cond-mat.stat-mech], 2000; J. Phys. A 33 (2000) 2587-2595.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).
%F First differences of A001629.
%F From _Wolfdieter Lang_, May 03 2000: (Start)
%F a(n) = ((2*n+3)*F(n) - n*F(n-1))/5, F(n)=A000045(n) (Fibonacci numbers) (Turban reference eq.(2.12)).
%F G.f.: x*(1-x)/(1-x-x^2)^2. (Turban reference eq.(2.10)). (End)
%F Recurrence: a(0)=0, a(1)=1, a(2)=1, a(n+2) = a(n+1) + a(n) + F(n). - _Benoit Cloitre_, Sep 02 2002
%F Set A(n) = a(n+1) + a(n-1), B(n) = a(n+1) - a(n-1). Then A(n+2) = A(n+1) + A(n) + Lucas(n) and B(n+2) = B(n+1) + B(n) + Fibonacci(n). The polynomials F_2(n,-x) = Sum_{k=0..n} C(n,k)*a(n-k)*(-x)^k appear to satisfy a Riemann hypothesis; their zeros appear to lie on the vertical line Re x = 1/2 in the complex plane. Compare with the polynomials F(n,-x) defined in A094440. For a similar conjecture for polynomials involving the second-order Lucas numbers see A134410. - _Peter Bala_, Oct 24 2007
%F a(n) = -A001629(n+2) + 2*A001629(n+1) + A000045(n+1). - _R. J. Mathar_, Nov 16 2007
%F Starting (1, 1, 3, 5, 10, ...), = row sums of triangle A135830. - _Gary W. Adamson_, Nov 30 2007
%F a(n) = F(n) + Sum_{k=0..n-1} F(k)*F(n-1-k), where F = A000045. - _Reinhard Zumkeller_, Nov 01 2013
%F a(n) = Sum_{k=0..n-1} (k+1)*binomial(n-k-1, k). - _Peter Luschny_, Nov 20 2013
%F a(n) = Sum_{i=0..n-1} Sum_{j=0..i} F(j-1)*F(i-j-1), where F = A000045. - _Carlos A. Rico A._, Jul 14 2016
%F a(n) = Sum_{k = F(n+1)..F(n+2)-1} A007895(k), where F(n) is the n-th Fibonacci number (Lekkerkerker, 1952). - _Amiram Eldar_, Jan 11 2020
%F a(n) = (1/5)*(n*A000032(n-1) + 3*A000045(n)). - _G. C. Greubel_, Apr 06 2022
%F E.g.f.: 2*exp(x/2)*(5*x*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2))/25. - _Stefano Spezia_, Dec 04 2023
%p with(combinat): A010049 := proc(n) options remember; if n <= 1 then n else A010049(n-1)+A010049(n-2)+fibonacci(n-2); fi; end;
%t CoefficientList[Series[(z - z^2)/(z^2 + z - 1)^2, {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jul 01 2011 *)
%t CoefficientList[Series[x (1 - x) / (1 - x - x^2)^2, {x, 0, 60}], x] (* _Vincenzo Librandi_, Jun 11 2013 *)
%t LinearRecurrence[{2, 1, -2, -1}, {0, 1, 1, 3}, 38] (* _Amiram Eldar_, Jan 11 2020 *)
%o (Haskell)
%o a010049 n = a010049_list !! n
%o a010049_list = uncurry c $ splitAt 1 a000045_list where
%o c us (v:vs) = (sum $ zipWith (*) us (1 : reverse us)) : c (v:us) vs
%o -- _Reinhard Zumkeller_, Nov 01 2013
%o (Sage)
%o def A010049():
%o a, b, c, d = 0, 1, 1, 3
%o while True:
%o yield a
%o a, b, c, d = b, c, d, 2*(d-b)+c-a
%o a = A010049(); [next(a) for i in range(38)] # _Peter Luschny_, Nov 20 2013
%o (PARI) a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-2,1,2]^n*[0;1;1;3])[1,1] \\ _Charles R Greathouse IV_, Jul 20 2016
%o (Magma) [((2*n+3)*Fibonacci(n)-n*Fibonacci(n-1))/5: n in [0..40]]; // _Vincenzo Librandi_, Dec 31 2018
%o (GAP) a:=List([0..40],n->Sum([0..n-1],k->(k+1)*Binomial(n-k-1,k)));; Print(a); # _Muniru A Asiru_, Dec 31 2018
%o (SageMath)
%o def A010049(n): return (1/5)*(n*lucas_number2(n-1, 1, -1) + 3*fibonacci(n))
%o [A010049(n) for n in (0..40)] # _G. C. Greubel_, Apr 06 2022
%Y Partial sums of A006367.
%Y Cf. A000032, A000045, A001629, A007895, A023610.
%Y Cf. A029907, A094440, A134410, A135830.
%K nonn,easy
%O 0,4
%A _N. J. A. Sloane_
%E More terms from _Emeric Deutsch_, Dec 10 2003