OFFSET
0,2
COMMENTS
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).
LINKS
Index entries for linear recurrences with constant coefficients, signature (0,2,0,4).
FORMULA
Recursive formula: a(0)=1, a(1)=2, a(2)=4, a(3)=6; for n > 3, a(n) = 2a(n-2) + 4a(n-4).
G.f.: -(2*x^3+2*x^2+2*x+1)/(4*x^4+2*x^2-1). - Alois P. Heinz, Dec 09 2016
a(n) = 2a(n-2) + 4a(n-4). - Charles R Greathouse IV, Dec 13 2016
EXAMPLE
a(3)=6; the 6 subsets of {1, 2, 3} that contain no consecutive odd integers are {}, {1}, {2}, {3}, {1,2}, {2,3}.
MATHEMATICA
LinearRecurrence[{0, 2, 0, 4}, {1, 2, 4, 6}, 40] (* Harvey P. Dale, Mar 21 2018 *)
PROG
(PARI) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 4, 0, 2, 0]^n*[1; 2; 4; 6])[1, 1] \\ Charles R Greathouse IV, Dec 13 2016
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Baris Arslan, Dec 08 2016
STATUS
approved