A279245 Number of subsets of {1, 2, 3, ..., n} that include no consecutive odd integers.

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

Author

Baris Arslan, Dec 08 2016

Keywords

• nonn
• easy

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

Examples

			a(3)=6; the 6 subsets of {1, 2, 3} that contain no consecutive odd integers are {}, {1}, {2}, {3}, {1,2}, {2,3}.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (0,2,0,4).

Programs

Mathematica

LinearRecurrence[{0,2,0,4},{1,2,4,6},40] (* Harvey P. Dale, Mar 21 2018 *)

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

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