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

%I #79 Aug 12 2024 13:20:21

%S 1,4,17,73,314,1351,5813,25012,107621,463069,1992482,8573203,36888569,

%T 158723236,682950473,2938582657,12644061866,54404561359,234090621197,

%U 1007239421908,4333925245949,18647907964021,80237764082258,345245096519227,1485512190349361

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

%C 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).

%C a(n) is the number of compositions of n when there are 4 types of ones. - _Milan Janjic_, Aug 13 2010

%C a(n)/a(n-1) tends to (5 + sqrt(13))/2 = 4.30277563... . - _Gary W. Adamson_, Jul 30 2013

%C 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

%C 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

%H Colin Barker, <a href="/A018902/b018902.txt">Table of n, a(n) for n = 0..1000</a>

%H D. W. Boyd, <a href="https://www.researchgate.net/profile/David_Boyd7/publication/262181133_Linear_recurrence_relations_for_some_generalized_Pisot_sequences_-_annotated_with_corrections_and_additions/links/00b7d536d49781037f000000.pdf">Linear recurrence relations for some generalized Pisot sequences</a>, Advances in Number Theory (Kingston ON, 1991) 333-340, Oxford Sci. Publ., Oxford Univ. Press, New York, 1993.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=474">Encyclopedia of Combinatorial Structures 474</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-3).

%H <a href="/index/Ph#Pisot">Index entries for Pisot sequences</a>

%F 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)).

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

%F O.g.f.: (1-x)/(1-5*x+3*x^2). - _R. J. Mathar_, Nov 23 2007

%F a(n) = 4*a(n-1) + a(n-2) + a(n-3) + a(n-4) + ... + a(0). - _Gary W. Adamson_, Aug 12 2013

%F 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

%F 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

%F 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

%t LinearRecurrence[{5,-3},{1,4},40] (* _Harvey P. Dale_, Jan 14 2012 *)

%o (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

%o (PARI) Vec((1-x) / (1-5*x+3*x^2) + O(x^30)) \\ _Colin Barker_, Jan 20 2017

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

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

%K nonn,easy

%O 0,2

%A _R. K. Guy_, _N. J. A. Sloane_