login
A279245
Number of subsets of {1, 2, 3, ..., n} that include no consecutive odd integers.
1
1, 2, 4, 6, 12, 20, 40, 64, 128, 208, 416, 672, 1344, 2176, 4352, 7040, 14080, 22784, 45568, 73728, 147456, 238592, 477184, 772096, 1544192, 2498560, 4997120, 8085504, 16171008, 26165248, 52330496, 84672512, 169345024, 274006016, 548012032, 886702080
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).
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
Sequence in context: A178901 A164146 A370582 * A090906 A047141 A341858
KEYWORD
nonn,easy
AUTHOR
Baris Arslan, Dec 08 2016
STATUS
approved