|
|
A010049
|
|
Second-order Fibonacci numbers.
|
|
21
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
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
|
|
|
FORMULA
|
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) = Sum_{k=0..n-1} (k+1)*binomial(n-k-1, k). - Peter Luschny, Nov 20 2013
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
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
|
|
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[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 *)
|
|
PROG
|
(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
(Sage)
a, b, c, d = 0, 1, 1, 3
while True:
yield a
a, b, c, d = b, c, d, 2*(d-b)+c-a
(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
(Magma) [((2*n+3)*Fibonacci(n)-n*Fibonacci(n-1))/5: n in [0..40]]; // Vincenzo Librandi, Dec 31 2018
(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
(SageMath)
def A010049(n): return (1/5)*(n*lucas_number2(n-1, 1, -1) + 3*fibonacci(n))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|