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

Author

John W. Layman, Jan 22 2010

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A005251, A005314.

Programs

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 *)

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

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