%I #96 Jan 03 2024 04:12:35
%S 1,1,6,11,41,96,301,781,2286,6191,17621,48576,136681,379561,1062966,
%T 2960771,8275601,23079456,64457461,179854741,502142046,1401415751,
%U 3912125981,10919204736,30479834641,85075858321,237475031526
%N Generalized Fibonacci numbers.
%C 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 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 From _Wolfdieter Lang_, Jan 02 2024: (Start)
%C 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 Limit_{n->oo} a(n)/a(n-1) = phi21. (End)
%H Vincenzo Librandi, <a href="/A015440/b015440.txt">Table of n, a(n) for n = 0..1000</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 14.8, pp. 317-318
%H 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 A. G. Shannon and J. V. Leyendekkers, <a href="http://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 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 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,5).
%F a(n) = a(n-1) + 5 a(n-2).
%F a(n) = (( (1+sqrt(21))/2 )^(n+1) - ( (1-sqrt(21))/2 )^(n+1))/sqrt(21).
%F a(n) = Sum_{k=0..ceiling(n/2)} 5^k*binomial(n-k, k). - _Benoit Cloitre_, Mar 06 2004
%F G.f.: 1/(1 - x - 5x^2). - _R. J. Mathar_, Sep 03 2008
%F a(n) = Sum_{k=0..n} A109466(n,k)*(-5)^(n-k). - _Philippe Deléham_, Oct 26 2008
%F From _Jeffrey R. Goodwin_, May 28 2011: (Start)
%F A special case of a more general class of Lucas sequences given by
%F U(n) = U(n-1) + (4^(m-1)-1)/3 U(n-2).
%F 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 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 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 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 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 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
%p A015440 := proc(n)
%p if n <= 1 then
%p 1;
%p else
%p procname(n-1)+5*procname(n-2) ;
%p end if;
%p end proc: # _R. J. Mathar_, May 15 2016
%t 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 LinearRecurrence[{1, 5}, {1, 1}, 100] (* _Vincenzo Librandi_, Nov 06 2012 *)
%o (Sage) [lucas_number1(n,1,-5) for n in range(1, 28)] # _Zerinvary Lajos_, Apr 22 2009
%o (Magma) [n le 2 select 1 else Self(n-1)+5*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Nov 06 2012
%o (PARI) a(n)=abs([1,3;1,-2]^n*[1;1])[2,1] \\ _Charles R Greathouse IV_, Feb 03 2014
%Y Cf. A006130, A006131, A015441, A049310, A222134, A365824.
%K nonn,easy
%O 0,3
%A _Olivier Gérard_