A131132 a(n) = a(n-1) + a(n-2) + 1 if n is a multiple of 6, otherwise a(n) = a(n-1) + a(n-2).

1, 1, 2, 3, 5, 8, 14, 22, 36, 58, 94, 152, 247, 399, 646, 1045, 1691, 2736, 4428, 7164, 11592, 18756, 30348, 49104, 79453, 128557, 208010, 336567, 544577, 881144, 1425722, 2306866, 3732588, 6039454, 9772042, 15811496, 25583539, 41395035, 66978574, 108373609

Offset

0,3

Comments

Also: convolution of A000045 with the period-6 sequence (0,0,0,0,0,0, 1,...). - R. J. Mathar, May 30 2008

Sequences of the form s(0)=a, s(1)= b, s(n) = s(n-1) + s(n-2) + k if n mod m = p, else s(n) = s(n-1) + s(n-2) have a form s(n) = fibonacci(n-1)*a + fibonacci(n)*b + P(x)*k. a(n) is the P(x) sequence for m=6. s(n) = fib(n)*a + fib(n-1)*b + a(n-6-p)*k. - Gary Detlefs, Dec 05 2010

a(n) is the number of compositions of n where the order of the 2 and the 3 does not matter. - Gregory L. Simay, May 18 2017

Links

Table of n, a(n) for n=0..39.

H. Matsui et al., Problem B-1035, Fibonacci Quarterly, Vol. 45, Number 2; 2007; p. 182.

Index entries for linear recurrences with constant coefficients, signature (1,1,0,0,0,1,-1,-1).

Formula

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

a(n) = ((-1)^n-1)/6 + A099837(n+3)/12 + A000045(n+4)/4 + A057079(n)/12. - R. J. Mathar, Dec 07 2010

a(n) = round((1 + sqrt(5))/8 A000045(n+3)). - John M. Campbell, Jul 06 2016

a(n) = (number of compositions of n consisting of only 1 or 2 or 6) - (number of compositions with only 7 or ((1 or 2) and 7)) - (number of compositions with only 8 or ((1 or 2) and 8)). The "or" is inclusive. - Gregory L. Simay, May 25 2017

Example

Since 5 is not a multiple of 6, a(5) = a(4) + a(3) = 5 + 3 = 8. Since 6 is a multiple of 6, a(6) = a(5) + a(4) + 1 = 8 + 5 + 1 = 14. - Michael B. Porter, Jul 26 2016

Maple

A131132:=proc(n) option remember; local t1; if n <= 2 then RETURN(1); fi: if n mod 6 = 1 then t1:=1 else t1:=0; fi: procname(n-1)+procname(n-2)+t1; end; [seq(A131132(n), n=1..100)]; # N. J. A. Sloane, May 25 2008; Typo corrected by R. J. Mathar, May 30 2008

Mathematica

Print[Table[Round[(1 + Sqrt[5])/8 Fibonacci[n + 3]], {n, 0, 50}]] ;
Print[RecurrenceTable[{c[n] == c[n - 1] + c[n - 2] + c[n - 6] - c[n - 7] - c[n - 8], c[0] == 1, c[1] == 1, c[2] == 2, c[3] == 3, c[4] == 5, c[5] == 8, c[6] == 14, c[7] == 22}, c, {n, 0, 50}]] ;  (* John M. Campbell, Jul 07 2016 *)
LinearRecurrence[{1, 1, 0, 0, 0, 1, -1, -1}, {1, 1, 2, 3, 5, 8, 14, 22}, 40] (* Vincenzo Librandi, Jul 07 2016 *)

Prog

(PARI) Vec(1/((1-x^6)*(1-x-x^2))+O(x^99)) \\ Charles R Greathouse IV, May 27 2026

Crossrefs

Cf. A052952, A004695, A080239, A124502, A066983, A099837, A000045, A057079.

Sequence in context: A000046 A293641 A293553 * A293545 A306274 A282240

Adjacent sequences: A131129 A131130 A131131 * A131133 A131134 A131135

Keyword

nonn,easy,changed

Author

N. J. A. Sloane, May 25 2008

Extensions

More specific name from R. J. Mathar, Dec 09 2009

Incorrect formula removed by Falk Hüffner, Jun 07 2026

Status

approved