A018902 a(n+2) = 5*a(n+1) - 3*a(n).

1, 4, 17, 73, 314, 1351, 5813, 25012, 107621, 463069, 1992482, 8573203, 36888569, 158723236, 682950473, 2938582657, 12644061866, 54404561359, 234090621197, 1007239421908, 4333925245949, 18647907964021, 80237764082258, 345245096519227, 1485512190349361

Offset: 0

Author

R. K. Guy, N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Define the sequence S(a(0),a(1)) by a(n+2) is the least integer such that a(n+2)/a(n+1) > a(n+1)/a(n) for n >= 0. This is S(1,4).

a(n) is the number of compositions of n when there are 4 types of ones. - Milan Janjic, Aug 13 2010

a(n)/a(n-1) tends to (5 + sqrt(13))/2 = 4.30277563... . - Gary W. Adamson, Jul 30 2013

a(n) counts closed walks on K_2 containing four loops on the index vertex and one loop on the other. Equivalently the (1,1)entry of A^(n) where the adjacency matrix of digraph is A=(4,1;1,1). - _David Neil McGrath, Nov 05 2014

Number of words of length n over {0,1,...,5} in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• D. W. Boyd, Linear recurrence relations for some generalized Pisot sequences, Advances in Number Theory (Kingston ON, 1991) 333-340, Oxford Sci. Publ., Oxford Univ. Press, New York, 1993.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 474
• Index entries for linear recurrences with constant coefficients, signature (5,-3).
• Index entries for Pisot sequences

Crossrefs

Equals (1/3)*A081704(n+1).

Cf. A006190 (shifted inverse binomial transform), A007052.

Programs

Magma

I:=[1, 4]; [n le 2 select I[n] else 5*Self(n-1)-3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 05 2014

Mathematica

LinearRecurrence[{5,-3},{1,4},40] (* Harvey P. Dale, Jan 14 2012 *)

PARI

Vec((1-x) / (1-5*x+3*x^2) + O(x^30)) \\ Colin Barker, Jan 20 2017

Formula

A member of the family of sequences defined by a(n) = (a(1)+1)*a(n-1) - (a(1)-1)*a(n-2). Alternatively, invert A007052 (invert: define b by 1 + Sum a(n)*x^n = 1/(1 - Sum b(n)*x^n)).

a(n+1)*a(n+1) - a(n+2)*a(n) = -3^n for n>0. - D. G. Rogers, Jul 11 2004

O.g.f.: (1-x)/(1-5*x+3*x^2). - R. J. Mathar, Nov 23 2007

a(n) = 4*a(n-1) + a(n-2) + a(n-3) + a(n-4) + ... + a(0). - Gary W. Adamson, Aug 12 2013

a(n) = (2^(-1-n)*((5-sqrt(13))^n*(-3+sqrt(13)) + (3+sqrt(13))*(5+sqrt(13))^n)) / sqrt(13). - Colin Barker, Jan 20 2017

E.g.f.: exp(5*x/2)*(13*cosh(sqrt(13)*x/2) + 3*sqrt(13)*sinh(sqrt(13)*x/2))/13. - Stefano Spezia, Jul 09 2022

a(n) = Fibonacci(2*n+1) + 2*Sum_{k=0..n-1} a(k)*Fibonacci(2*(n-1-k)+1). - Greg Dresden and Mulong Xu, Aug 10 2024