A172020 Number of subsets S of {1,2,3,...,n} with the property that if x is a member of S then at least one of x-2 and x+2 is also a member of S.

1, 1, 2, 4, 8, 16, 28, 49, 84, 144, 252, 441, 777, 1369, 2405, 4225, 7410, 12996, 22800, 40000, 70200, 123201, 216216, 379456, 665896, 1168561, 2050657, 3598609, 6315113, 11082241, 19448018, 34128964, 59892184, 105103504, 184443732, 323676081, 568011852

Offset

1,3

Comments

It is interesting that, for k > 0, it appears that a(2k) is the square of A005251(k+2). (This has since been proved by Andrew Weimholt; see link.)

If we denote by d2 the second difference of {a(n)}, it appears that d2(2k) is the square of A005314(k).

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Proof by Andrew Weimholt, SeqFan Jan 2010

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

Formula

Andrew Weimholt has shown that a(2*n) = A005251(n+2) ^ 2, and a(2*n+1) = A005251(n+2) * A005251(n+3). (See the link.)

G.f.: x*(1 - x + x^3 + 2*x^4 - x^8) / ((1 - 2*x + x^2 - x^3)*(1 + x - x^3)*(1 - x + x^3)). - Colin Barker, Feb 15 2016

Mathematica

LinearRecurrence[{2, 0, -1, -1, 3, -1, 0, 1, -1}, {1, 1, 2, 4, 8, 16, 28, 49, 84}, 32] (* Jean-François Alcover, Feb 15 2016 *)

Prog

(PARI) Vec(x*(1-x+x^3+2*x^4-x^8)/((1-2*x+x^2-x^3)*(1+x-x^3)*(1-x+x^3)) + O(x^50)) \\ Colin Barker, Feb 15 2016

Crossrefs

Cf. A005251, A005314.

Sequence in context: A112128 A208933 A227036 * A209410 A228733 A318767

Adjacent sequences: A172017 A172018 A172019 * A172021 A172022 A172023

Keyword

nonn,easy

Author

John W. Layman, Jan 22 2010

Status

approved