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,2

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

Links

Table of n, a(n) for n=0..30.

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

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

Example

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

Prog

(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

Crossrefs

Cf. A279245

Sequence in context: A343419 A353796 A294067 * A326076 A181808 A343014

Adjacent sequences: A279309 A279310 A279311 * A279313 A279314 A279315

Keyword

nonn,easy

Author

Baris Arslan, Dec 09 2016

Extensions

More terms from Charles R Greathouse IV, Dec 13 2016

Edited by Michel Marcus, Jul 04 2017

Status

approved