cp's OEIS Frontend

A010049 Second-order Fibonacci numbers.

%I A010049 #125 Nov 14 2024 15:18:10
%S A010049 0,1,1,3,5,10,18,33,59,105,185,324,564,977,1685,2895,4957,8462,14406,
%T A010049 24465,41455,70101,118321,199368,335400,563425,945193,1583643,2650229,
%U A010049 4430290,7398330,12342849,20573219,34262337,57013865,94800780,157517532,261545777
%N A010049 Second-order Fibonacci numbers.
%C A010049 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 A010049 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 83.
%D A010049 Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin, Vol. 29 (1952), pp. 190-195.
%H A010049 Vincenzo Librandi, <a href="/A010049/b010049.txt">Table of n, a(n) for n = 0..1000</a>
%H A010049 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 A010049 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 A010049 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 A010049 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 A010049 Jia Huang, <a href="https://arxiv.org/abs/1812.11010">Compositions with restricted parts</a>, arXiv:1812.11010 [math.CO], 2018.
%H A010049 Tamás Szakács, <a href="https://hdl.handle.net/2437/381856">Linear recursive sequences and factorials</a>, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See pp. 2, 50, 57.
%H A010049 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 A010049 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).
%F A010049 First differences of A001629.
%F A010049 From _Wolfdieter Lang_, May 03 2000: (Start)
%F A010049 a(n) = ((2*n+3)*F(n) - n*F(n-1))/5, F(n)=A000045(n) (Fibonacci numbers) (Turban reference eq.(2.12)).
%F A010049 G.f.: x*(1-x)/(1-x-x^2)^2. (Turban reference eq.(2.10)). (End)
%F A010049 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 A010049 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 A010049 a(n) = -A001629(n+2) + 2*A001629(n+1) + A000045(n+1). - _R. J. Mathar_, Nov 16 2007
%F A010049 Starting (1, 1, 3, 5, 10, ...), = row sums of triangle A135830. - _Gary W. Adamson_, Nov 30 2007
%F A010049 a(n) = F(n) + Sum_{k=0..n-1} F(k)*F(n-1-k), where F = A000045. - _Reinhard Zumkeller_, Nov 01 2013
%F A010049 a(n) = Sum_{k=0..n-1} (k+1)*binomial(n-k-1, k). - _Peter Luschny_, Nov 20 2013
%F A010049 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 A010049 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 A010049 a(n) = (1/5)*(n*A000032(n-1) + 3*A000045(n)). - _G. C. Greubel_, Apr 06 2022
%F A010049 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 A010049 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 A010049 CoefficientList[Series[(z - z^2)/(z^2 + z - 1)^2, {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jul 01 2011 *)
%t A010049 CoefficientList[Series[x (1 - x) / (1 - x - x^2)^2, {x, 0, 60}], x] (* _Vincenzo Librandi_, Jun 11 2013 *)
%t A010049 LinearRecurrence[{2, 1, -2, -1}, {0, 1, 1, 3}, 38] (* _Amiram Eldar_, Jan 11 2020 *)
%o A010049 (Haskell)
%o A010049 a010049 n = a010049_list !! n
%o A010049 a010049_list = uncurry c $ splitAt 1 a000045_list where
%o A010049    c us (v:vs) = (sum $ zipWith (*) us (1 : reverse us)) : c (v:us) vs
%o A010049 -- _Reinhard Zumkeller_, Nov 01 2013
%o A010049 (Sage)
%o A010049 def A010049():
%o A010049     a, b, c, d = 0, 1, 1, 3
%o A010049     while True:
%o A010049         yield a
%o A010049         a, b, c, d = b, c, d, 2*(d-b)+c-a
%o A010049 a = A010049(); [next(a) for i in range(38)]  # _Peter Luschny_, Nov 20 2013
%o A010049 (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 A010049 (Magma) [((2*n+3)*Fibonacci(n)-n*Fibonacci(n-1))/5: n in [0..40]]; // _Vincenzo Librandi_, Dec 31 2018
%o A010049 (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 A010049 (SageMath)
%o A010049 def A010049(n): return (1/5)*(n*lucas_number2(n-1, 1, -1) + 3*fibonacci(n))
%o A010049 [A010049(n) for n in (0..40)] # _G. C. Greubel_, Apr 06 2022
%Y A010049 Partial sums of A006367.
%Y A010049 Cf. A000032, A000045, A001629, A007895, A023610.
%Y A010049 Cf. A029907, A094440, A134410, A135830.
%K A010049 nonn,easy
%O A010049 0,4
%A A010049 _N. J. A. Sloane_
%E A010049 More terms from _Emeric Deutsch_, Dec 10 2003