A045925 a(n) = n*Fibonacci(n).

0, 1, 2, 6, 12, 25, 48, 91, 168, 306, 550, 979, 1728, 3029, 5278, 9150, 15792, 27149, 46512, 79439, 135300, 229866, 389642, 659111, 1112832, 1875625, 3156218, 5303286, 8898708, 14912641, 24961200, 41734339, 69705888, 116311074, 193898158, 322961275, 537492672

Offset

0,3

Comments

Number of levels in all compositions of n+1 with only 1's and 2's.

Apart from first term: row sums of the triangle in A131410. - Reinhard Zumkeller, Oct 07 2012

Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the third one. - Sergey Kitaev, Dec 08 2020

References

Jean Paul Van Bendegem, The Heterogeneity of Mathematical Research, a chapter in Perspectives on Interrogative Models of Inquiry, Volume 8 of the series Logic, Argumentation & Reasoning pp 73-94, Springer 2015. See Section 2.1.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Russell Euler, Problem B-670, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 28, No. 3 (1990), p. 277; Application of Generating Functions, Solution to Problem B-670 by Russell Jay Hendel, ibid., Vol. 29, No. 3 (1991), p. 278.

Rigoberto Flórez, Robinson Higuita and Alexander Ramírez, The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials, arXiv:1808.01264 [math.NT], 2018.

Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics, Vol. 26, No. 3 (2019), Article P3.26.

Silvia Heubach and Toufik Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.

Kai Ting Keshia Yap, David Wehlau and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.

Index to divisibility sequences.

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Formula

G.f.: x*(1+x^2)/(1-x-x^2)^2.

G.f.: Sum_{n>=1} phi(n)*Fibonacci(n)*x^n/(1 - Lucas(n)*x^n + (-1)^n*x^(2*n)) = Sum_{n>=1} n*Fibonacci(n)*x^n, where phi(n) = A000010(n) and Lucas(n) = A000204(n). - Paul D. Hanna, Jan 12 2012

a(n) = a(n-1) + a(n-2) + L(n-1). - Gary Detlefs, Dec 29 2012

a(n) = F(n+1) + Sum_{k=1..n-2} F(k)*L(n-k), F = A000045 and L = A000032. - Gary Detlefs, Dec 29 2012

a(n) = F(2*n)/Sum_{k=0..floor(n/2)} binomial(n-k,k)/(n-k). - Gary Detlefs, Jan 19 2013

a(n) = A014965(n) * A104714(n). - Michel Marcus, Oct 24 2013

a(n) = 3*A001629(n+1) - A001629(n+2) + A000045(n-1). - Ralf Stephan, Apr 26 2014

a(n) = 2*n*(F(n-2) + floor(F(n-3)/2)) + (n^3 mod 3*n), F = A000045. - Gary Detlefs, Jun 06 2014

E.g.f.: x*(exp(-x/phi)/phi + exp(x*phi)*phi)/sqrt(5), where phi = (1+sqrt(5))/2. - Vladimir Reshetnikov, Oct 28 2015

This is a divisibility sequence and is generated by x^4 - 2*x^3 - x^2 + 2*x + 1. - R. K. Guy, Nov 13 2015

a(n) = L'(n, 1), the first derivative of the n-th Lucas polynomial evaluated at 1. - Andrés Ventas, Nov 12 2021

Sum_{n>=0} a(n)/2^n = 10 (Euler, 1990). - Amiram Eldar, Jan 22 2022

Maple

a:= n-> n*(<<0|1>, <1|1>>^n)[1, 2]:
seq(a(n), n=0..37);  # Alois P. Heinz, May 07 2021

Mathematica

Table[Fibonacci[n]*n, {n, 0, 33}] (* Zerinvary Lajos, Jul 09 2009] *)
LinearRecurrence[{2, 1, -2, -1}, {0, 1, 2, 6}, 34] (* or *)
CoefficientList[ Series[(x + x^3)/(-1 + x + x^2)^2, {x, 0, 35}], x] (* Robert G. Wilson v, Nov 14 2015 *)

Prog

(Magma) [n*Fibonacci(n): n in [0..60]]; // Vincenzo Librandi, Apr 23 2011
(PARI) Lucas(n)=fibonacci(n-1)+fibonacci(n+1)
a(n)=polcoeff(sum(m=1, n, eulerphi(m)*fibonacci(m)*x^m/(1-Lucas(m)*x^m+(-1)^m*x^(2*m)+x*O(x^n))), n) \\ Paul D. Hanna, Jan 12 2012
(PARI) a(n)=n*fibonacci(n) \\ Charles R Greathouse IV, Jan 12 2012
(PARI) concat(0, Vec(x*(1+x^2)/(1-x-x^2)^2 + O(x^100))) \\ Altug Alkan, Oct 28 2015
(Haskell)
a045925 n = a045925_list !! (n-1)
a045925_list = zipWith (*) [0..] a000045_list
-- Reinhard Zumkeller, Oct 01 2012

Crossrefs

Partial sums: A014286. Cf. A000045.

Cf. A099920, A023607.

Sequence in context: A262196 A261667 A116562 * A128020 A140659 A238462

Adjacent sequences: A045922 A045923 A045924 * A045926 A045927 A045928

Keyword

nonn,easy

Author

Jeff Burch

Extensions

Incorrect formula removed by Gary Detlefs, Oct 27 2011

Status

approved