cp's OEIS Frontend

A015440 a(n) = a(n-1) + 5*a(n-2), with a(0) = a(1) = 1.

%I A015440 #124 Jul 06 2025 10:02:45
%S A015440 1,1,6,11,41,96,301,781,2286,6191,17621,48576,136681,379561,1062966,
%T A015440 2960771,8275601,23079456,64457461,179854741,502142046,1401415751,
%U A015440 3912125981,10919204736,30479834641,85075858321,237475031526,662854323131,1850229480761,5164501096416
%N A015440 a(n) = a(n-1) + 5*a(n-2), with a(0) = a(1) = 1.
%C A015440 Original name: Generalized Fibonacci numbers.
%C A015440 The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 2, 6*a(n-2) equals the number of 6-colored compositions of n with all parts >= 2, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 26 2011
%C A015440 Pisano period lengths: 1, 3, 6, 6, 1, 6, 21, 12, 18, 3, 40, 6, 56, 21, 6, 24, 16, 18, 360, 6, .... - _R. J. Mathar_, Aug 10 2012
%C A015440 From _Wolfdieter Lang_, Jan 02 2024: (Start)
%C A015440 This sequence {a(n-1)}, with a(-1) = 0, appears in the formula for powers of phi21 := (1 + sqrt(21))/2 = A222134 = 2.791287..., together with A(n) = A365824(n), as phi21^n = A(n) + a(n-1)*phi21(n), for n >= 0.
%C A015440 Limit_{n->oo} a(n)/a(n-1) = phi21. (End)
%H A015440 Vincenzo Librandi, <a href="/A015440/b015440.txt">Table of n, a(n) for n = 0..1000</a>
%H A015440 Joerg Arndt, <a href="https://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 14.8, pp. 317-318
%H A015440 Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H A015440 A. G. Shannon and J. V. Leyendekkers, <a href="https://nntdm.net/volume-21-2015/number-2/35-42/">The Golden Ratio family and the Binet equation</a>, Notes on Number Theory and Discrete Mathematics, Vol. 21, No. 2, (2015), 35-42.
%H A015440 Paul Thomas Young, <a href="https://www.fq.math.ca/Scanned/32-1/young.pdf">p-adic congruences for generalized Fibonacci sequences</a>, The Fibonacci Quarterly, Vol. 32, No. 1, 1994.
%H A015440 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,5).
%F A015440 a(n) = a(n-1) + 5*a(n-2).
%F A015440 a(n) = (( (1+sqrt(21))/2 )^(n+1) - ( (1-sqrt(21))/2 )^(n+1))/sqrt(21).
%F A015440 a(n) = Sum_{k=0..ceiling(n/2)} 5^k*binomial(n-k, k). - _Benoit Cloitre_, Mar 06 2004
%F A015440 G.f.: 1/(1 - x - 5x^2). - _R. J. Mathar_, Sep 03 2008
%F A015440 a(n) = Sum_{k=0..n} A109466(n,k)*(-5)^(n-k). - _Philippe Deléham_, Oct 26 2008
%F A015440 From _Jeffrey R. Goodwin_, May 28 2011: (Start)
%F A015440 A special case of a more general class of Lucas sequences given by
%F A015440 U(n) = U(n-1) + (4^(m-1)-1)/3 U(n-2).
%F A015440 U(n) = (( (1+sqrt((4^(m)-1)/3))/2 )^(n+1) - ( (1-sqrt((4^(m)-1)/3))/2 )^(n+1))/sqrt((4^(m)-1)/3). Fix m = 2 to get the formula for the Fibonacci sequence, fix m = 3 to get the formula for a(n). (End)
%F A015440 G.f.: G(0)/(2-x), where G(k)= 1 + 1/(1 - x*(21*k-1)/(x*(21*k+20) - 2/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 20 2013
%F A015440 G.f.: Q(0)/x -1/x, where Q(k) = 1 + 5*x^2 + (k+2)*x - x*(k+1 + 5*x)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 06 2013
%F A015440 a(n) = (Sum_{k=1..n+1, k odd} binomial(n+1,k)*21^((k-1)/2))/2^n. - _Vladimir Shevelev_, Feb 05 2014
%F A015440 With an initial 0 prepended, the sequence [0, 1, 1, 6, 11, 41, 96, ...] satisfies the congruences a(n*p^k) == (3|p)*(7|p)*a(n*p^(k-1)) (mod p^k) for positive integers k and n and all primes p, where (n|p) denotes the Legendre symbol. See Young, Theorem 1, Corollary 1(i). - _Peter Bala_, Dec 28 2022
%F A015440 a(n) = sqrt(-5)^(n-1)*S(n-1,1/sqrt(-5)), for n >= 0, with the Chebyshev polynomial S(n, x) (see A049310). - _Wolfdieter Lang_, Nov 17 2023
%F A015440 From _Peter Bala_, Jun 27 2025: (Start)
%F A015440 The following products telescope:
%F A015440 Product_{k >= 0} (1 + 5^k/a(2*k+1)) = 1 + sqrt(21).
%F A015440 Product_{k >= 1} (1 - 5^k/a(2*k+1)) = 1/22 * (1 + sqrt(21)).
%F A015440 Product_{k >= 0} (1 + (-5)^k/a(2*k+1)) = (1/21) * (21 + sqrt(21)).
%F A015440 Product_{k >= 1} (1 - (-5)^k/a(2*k+1)) = (1/22) * (21 + sqrt(21)). (End)
%F A015440 E.g.f.: exp(x/2)*(sqrt(21)*cosh(sqrt(21)*x/2) + sinh(sqrt(21)*x/2))/sqrt(21). - _Stefano Spezia_, Jul 04 2025
%p A015440 A015440 := proc(n)
%p A015440     if n <= 1 then
%p A015440         1;
%p A015440     else
%p A015440         procname(n-1)+5*procname(n-2) ;
%p A015440     end if;
%p A015440 end proc: # _R. J. Mathar_, May 15 2016
%t A015440 a[n_]:=(MatrixPower[{{1,3},{1,-2}},n].{{1},{1}})[[2,1]]; Table[Abs[a[n]],{n,-1,40}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 19 2010 *)
%t A015440 LinearRecurrence[{1, 5}, {1, 1}, 100] (* _Vincenzo Librandi_, Nov 06 2012 *)
%o A015440 (Sage) [lucas_number1(n,1,-5) for n in range(1, 28)] # _Zerinvary Lajos_, Apr 22 2009
%o A015440 (Magma) [n le 2 select 1 else Self(n-1)+5*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Nov 06 2012
%o A015440 (PARI) a(n)=abs([1,3;1,-2]^n*[1;1])[2,1] \\ _Charles R Greathouse IV_, Feb 03 2014
%Y A015440 Cf. A006130, A006131, A015441, A049310, A222134, A365824.
%K A015440 nonn,easy
%O A015440 0,3
%A A015440 _Olivier Gérard_