A010049 Second-order Fibonacci numbers.

0, 1, 1, 3, 5, 10, 18, 33, 59, 105, 185, 324, 564, 977, 1685, 2895, 4957, 8462, 14406, 24465, 41455, 70101, 118321, 199368, 335400, 563425, 945193, 1583643, 2650229, 4430290, 7398330, 12342849, 20573219, 34262337, 57013865, 94800780, 157517532, 261545777

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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

References

• D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 83.
• Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin, Vol. 29 (1952), pp. 190-195.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Carlos A. Rico A. and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
• T. Amdeberhan and M. B. Can, M. Jensen, Divisors and specializations of Lucas polynomials, arXiv preprint arXiv:1406.0432 [math.CO], 2014.
• Kálmán Liptai, László Németh, Tamás Szakács, and László Szalay, On certain Fibonacci representations, arXiv:2403.15053 [math.NT], 2024. See p. 2.
• Mengmeng Liu and Andrew Yezhou Wang, The Number of Designated Parts in Compositions with Restricted Parts, J. Int. Seq., Vol. 23 (2020), Article 20.1.8.
• Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
• Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See pp. 2, 50, 57.
• Loïc Turban, Lattice animals on a staircase and Fibonacci numbers, arXiv:cond-mat/0011038 [cond-mat.stat-mech], 2000; J. Phys. A 33 (2000) 2587-2595.
• Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Crossrefs

Partial sums of A006367.

Cf. A000032, A000045, A001629, A007895, A023610.

Cf. A029907, A094440, A134410, A135830.

Programs

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

Haskell

a010049 n = a010049_list !! n
a010049_list = uncurry c $ splitAt 1 a000045_list where
   c us (v:vs) = (sum $ zipWith (*) us (1 : reverse us)) : c (v:us) vs
-- Reinhard Zumkeller, Nov 01 2013

Magma

[((2*n+3)*Fibonacci(n)-n*Fibonacci(n-1))/5: n in [0..40]]; // Vincenzo Librandi, Dec 31 2018

Maple

with(combinat): A010049 := proc(n) options remember; if n <= 1 then n else A010049(n-1)+A010049(n-2)+fibonacci(n-2); fi; end;

Mathematica

CoefficientList[Series[(z - z^2)/(z^2 + z - 1)^2, {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)
CoefficientList[Series[x (1 - x) / (1 - x - x^2)^2, {x, 0, 60}], x] (* Vincenzo Librandi, Jun 11 2013 *)
LinearRecurrence[{2, 1, -2, -1}, {0, 1, 1, 3}, 38] (* Amiram Eldar, Jan 11 2020 *)

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

Sage

def A010049():
    a, b, c, d = 0, 1, 1, 3
    while True:
        yield a
        a, b, c, d = b, c, d, 2*(d-b)+c-a
a = A010049(); [next(a) for i in range(38)]  # Peter Luschny, Nov 20 2013

SageMath

def A010049(n): return (1/5)*(n*lucas_number2(n-1, 1, -1) + 3*fibonacci(n))
[A010049(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

Formula

First differences of A001629.

From Wolfdieter Lang, May 03 2000: (Start)

a(n) = ((2*n+3)*F(n) - n*F(n-1))/5, F(n)=A000045(n) (Fibonacci numbers) (Turban reference eq.(2.12)).

G.f.: x*(1-x)/(1-x-x^2)^2. (Turban reference eq.(2.10)). (End)

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

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

a(n) = -A001629(n+2) + 2*A001629(n+1) + A000045(n+1). - R. J. Mathar, Nov 16 2007

Starting (1, 1, 3, 5, 10, ...), = row sums of triangle A135830. - Gary W. Adamson, Nov 30 2007

a(n) = F(n) + Sum_{k=0..n-1} F(k)*F(n-1-k), where F = A000045. - Reinhard Zumkeller, Nov 01 2013

a(n) = Sum_{k=0..n-1} (k+1)*binomial(n-k-1, k). - Peter Luschny, Nov 20 2013

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

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

a(n) = (1/5)*(n*A000032(n-1) + 3*A000045(n)). - G. C. Greubel, Apr 06 2022

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

Extensions

More terms from Emeric Deutsch, Dec 10 2003