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

0, 1, 1, 8, 15, 71, 176, 673, 1905, 6616, 19951, 66263, 205920, 669761, 2111201, 6799528, 21577935, 69174631, 220220176, 704442593, 2245983825, 7177081976, 22898968751, 73138542583, 233431323840, 745401121921, 2379420388801

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

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

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

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

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Joerg Arndt, Matters Computational (The Fxtbook), section 14.8 "Strings with no two consecutive nonzero digits", pp.317-318
• Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Index entries for linear recurrences with constant coefficients, signature (1,7).

Crossrefs

Cf. A015440, A015441, A049310.

Programs

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

Mathematica

LinearRecurrence[{1, 7}, {0, 1}, 30] (* Vincenzo Librandi, Oct 17 2012 *)
nxt[{a_,b_}]:={b,7a+b}; NestList[nxt,{0,1},30][[All,1]] (* Harvey P. Dale, Feb 25 2022 *)

PARI

concat(0,Vec(1/(1-x-7*x^2)+O(x^99))) \\ Charles R Greathouse IV, Mar 12 2014

Sage

[lucas_number1(n,1,-7) for n in range(0, 27)] # Zerinvary Lajos, Apr 22 2009

Formula

O.g.f.: x/(1-x-7x^2). - R. J. Mathar, May 06 2008

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

a(n) = 8*a(n-2) + 7*a(n-3) with characteristic polynomial x^3 - 8*x - 7. - Roger L. Bagula, May 30 2007

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

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

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