login
a(n) = a(n-1) + 7*a(n-2), a(0)=0, a(1)=1.
19

%I #74 Aug 04 2024 18:50:54

%S 0,1,1,8,15,71,176,673,1905,6616,19951,66263,205920,669761,2111201,

%T 6799528,21577935,69174631,220220176,704442593,2245983825,7177081976,

%U 22898968751,73138542583,233431323840,745401121921,2379420388801

%N a(n) = a(n-1) + 7*a(n-2), a(0)=0, a(1)=1.

%C One obtains A015523 through a binomial transform, and A197189 by shifting one place left (starting 1,1,8 with offset 0) followed by a binomial transform. - _R. J. Mathar_, Oct 11 2011

%C The compositions of n in which each positive integer is colored by one of p different colors are called p-colored compositions of n. For n>=2, 8*a(n-1) equals the number of 8-colored compositions of n, with all parts >=2, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 26 2011

%C a(n+1) is the number of compositions (ordered partitions) of n into parts 1 and 2, where there are 7 sorts of part 2. - _Joerg Arndt_, Jan 16 2024

%C Pisano period lengths: 1, 3, 8, 6, 4, 24, 1, 6, 24, 12, 60, 24, 12, 3, 8, 6, 288, 24, 120, 12, ... - _R. J. Mathar_, Aug 10 2012

%H Vincenzo Librandi, <a href="/A015442/b015442.txt">Table of n, a(n) for n = 0..1000</a>

%H Joerg Arndt, <a href="https://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 14.8 "Strings with no two consecutive nonzero digits", 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 href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,7).

%F O.g.f.: x/(1-x-7x^2). - _R. J. Mathar_, May 06 2008

%F a(n) = ( ((1+sqrt(29))/2)^(n+1) - ((1-sqrt(29))/2)^(n+1) )/sqrt(29).

%F a(n) = 8*a(n-2) + 7*a(n-3) with characteristic polynomial x^3 - 8*x - 7. - _Roger L. Bagula_, May 30 2007

%F a(n+1) = Sum_{k=0..n} A109466(n,k)*(-7)^(n-k). - _Philippe Deléham_, Oct 26 2008

%F a(n) = (Sum_{1<=k<=n, k odd} C(n,k)*29^((k-1)/2))/2^(n-1). - _Vladimir Shevelev_, Feb 05 2014

%F a(n) = sqrt(-7)^(n-1)*S(n-1, 1/sqrt(-7)), with the Chebyshev polynomial S(n, x), and S(-1, x) = 1 (see A049310). - _Wolfdieter Lang_, Nov 26 2023

%t LinearRecurrence[{1, 7}, {0, 1}, 30] (* _Vincenzo Librandi_, Oct 17 2012 *)

%t nxt[{a_,b_}]:={b,7a+b}; NestList[nxt,{0,1},30][[All,1]] (* _Harvey P. Dale_, Feb 25 2022 *)

%o (Sage) [lucas_number1(n,1,-7) for n in range(0, 27)] # _Zerinvary Lajos_, Apr 22 2009

%o (Magma) I:=[0, 1]; [n le 2 select I[n] else Self(n-1) + 7*Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Oct 17 2012

%o (PARI) concat(0,Vec(1/(1-x-7*x^2)+O(x^99))) \\ _Charles R Greathouse IV_, Mar 12 2014

%Y Cf. A015440, A015441, A049310.

%K nonn,easy

%O 0,4

%A _Olivier Gérard_