a(n) is the number of subsets T of A = {1, 2, ..., 2*n} such that no pair of elements a, b of T satisfy |a-b| = 1 or n. Proof: Suppose that n >= 3. Let b(n) be the number of ways to choose points on a 2 X n lattice such that the points do not touch each other. Let c(n) be the number of ways to choose points on a 2 X n lattice eliminating the upper left corner such that the points do not touch each other. Let d(n) be the number of ways to choose points on a 2 X n lattice eliminating the upper left and lower right corners such that the points do not touch each other. Put the numbers on the 2 X n lattice: 1 2 ... n n+1 n+2 ... 2*n For a(n), the selected points from T do not touch each other, amounting to b(n) ways. We should only eliminate the case that n and n+1 are both chosen. So 1, n-1, n+2, 2*n must not be chosen, and the remaining lattice corresponds to d(n-1). Hence a(n) = b(n) - d(n-1). (1) For b(n), if 1 and n+1 are not chosen, the remaining lattice corresponds to b(n-1); if 1 is chosen, 2 and n+1 must not be chosen, and the remaining lattice corresponds to c(n-1). Hence b(n) = b(n-1) + 2*c(n-1). (2) For c(n), if n+1 is not chosen, the remaining lattice corresponds to b(n-1); if n+1 is chosen, n+2 must not be chosen, and the remaining lattice corresponds to c(n-1). Hence c(n) = b(n-1) + c(n-1). (3) For d(n), if n+1 is not chosen, the remaining lattice corresponds to c(n-1); if n+1 is chosen, n+2 must not be chosen. If 2 is not chosen, the remaining lattice corresponds to c(n-2); if 2 is chosen, 3 must not be chosen, and the remaining lattice corresponds to d(n-2). Hence d(n) = c(n-1) + c(n-2) + d(n-2). (4) From (2) - (3), b(n) - c(n) = c(n-1). (5) From (2), c(n-1) = (b(n) - b(n-1))/2. (6) Substitute (6) into (5), b(n) = 2*b(n-1) + b(n-2). (7) Since b(0) = 1, b(1) = 3, b(n) = A001333(n+1). Substitute (5) into (3), c(n) = 2*c(n-1) + c(n-2). (8) Since c(0) = 1, c(1) = 2, c(n) = A000129(n+1). Substitute (5) into (4), d(n) = b(n-1) + d(n-2). (9) Substitute (7) into (9), d(n) = d(n-2) + (b(n) - b(n-2))/2. So d(n) - b(n)/2 = d(n-2) - b(n-2)/2. If n is even, d(n) - b(n)/2 = d(2) - b(2)/2 = 1/2; If n is odd, d(n) - b(n)/2 = d(1) - b(1)/2 = -1/2. Hence d(n) = b(n)/2 + (-1)^n/2. (10) From (7), b(n) = ((1-sqrt(2))^(n+1) + (1+sqrt(2))^(n+1))/2. (11) Substitute (11) into (10) and (1), a(n) = 1/4*((3+sqrt(2))*(1+sqrt(2))^n+(3-sqrt(2))*(1-sqrt(2))^n-2*(-1)^n), d(n) = ((1+sqrt(2))^n + (1-sqrt(2))^n - 2*(-1)^n)/4. Therefore, d(n) = d(n-1) + 3*d(n-2) + d(n-3) with d(0) = 1, d(1) = 1, d(2) = 4, so d(n) = A097076(n+1), a(n) = a(n-1) + 3*a(n-2) + a(n-3) with a(0) = 1, a(1) = 3, a(2) = 6.