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

1, 2, 4, 8, 12, 24, 40, 80, 128, 256, 416, 832, 1344, 2688, 4352, 8704, 14080, 28160, 45568, 91136, 147456, 294912, 477184, 954368, 1544192, 3088384, 4997120, 9994240, 16171008, 32342016, 52330496

Offset: 0

Author

Baris Arslan, Dec 09 2016

Keywords

• nonn
• easy

Comments

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

Examples

			For n=4, a(n)=12. The number of subsets of {1, 2, 3, 4} that include no consecutive even integers are: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}.
		

Links

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

Crossrefs

Cf. A279245

Programs

Mathematica

LinearRecurrence[{0,2,0,4},{1,2,4,8},40] (* Harvey P. Dale, Mar 30 2025 *)

PARI

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 4,0,2,0]^n*[1;2;4;8])[1,1] \\ Charles R Greathouse IV, Dec 13 2016

Formula

a(n) = A279245(n) if n is even; a(n) = 2*A279245(n-1) if n is odd.

G.f.: (2*x^3+4*x^2+2*x+2)/(4*x^4+2*x^2-1).

a(n) = 2a(n-2) + 4a(n-4). - Charles R Greathouse IV, Dec 13 2016

Extensions

More terms from Charles R Greathouse IV, Dec 13 2016

Edited by Michel Marcus, Jul 04 2017