cp's OEIS Frontend

Let b(n) be the number of subsets of [n] that include no consecutive odd integers then b(n) satisfies the recurrence b(0)=1, b(1)=2, b(2)=4, b(3)=6; for n > 3, b(n) = 2b(n-2) + 4b(n-4). For that sequence see A279245.

Let a(n) be the number of subsets of [n] that include no consecutive even integers. If n is an even integer then, a(n) = b(n). Since in the set S = {1, 2, 3, ..., n} where n is even, the number of odd integers is equal to the number of even integers. For example, let S ={1, 2, 3, 4} In this set there are 2 odd and 2 even integers. So the number of subsets of S contain no consecutive odd integers is equal to the number of subsets of S contain no consecutive even integers. In the other case if n is an odd integer then, a(n) = 2b(n-1). Since in the set S = {1, 2, 3, ..., n} where n is odd; Let K = {1, 2, 3, ..., n-1}, n-1 is an even integer so there are b(n-1) subsets containing no consecutive even integers in the set K. And prepending the last element 'n' to each of those gives us another b(n-1) subsets, for a total of 2b(n-1) subsets. Hence if n is even then, a(n) = b(n). If n is odd then, a(n) = 2b(n-1). For k = 0, 1, 2, 3, ... ; a(2k+1) = 2a(2k).

For n>3 there are 2 cases for the subsets: the first element '1' is included or not. If '1' is not included, then the subset consists of elements from {2, 3, 4, ..., n}. The number of subsets that include no element smaller than '3' is a(n-2); prepending the element '2' to each of those gives us another a(n-2) subsets, for a total of 2a(n-2) subsets. In the other case, '1' is included, and since 1 and 3 are consecutive odd integers, '3' is excluded, so the subset consists of elements from {1, 2, 4, 5, ..., n}. The number of subsets that include no element smaller than '5' is a(n-4), and since there are 2^2=4 subsets of {2, 4}, the number of subsets that include '1' is 4a(n-4). Hence a(n) = 2a(n-2) + 4a(n-4).