

A279312


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


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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(n2) + 4b(n4). 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(n1). Since in the set S = {1, 2, 3, ..., n} where n is odd; Let K = {1, 2, 3, ..., n1}, n1 is an even integer so there are b(n1) subsets containing no consecutive even integers in the set K. And prepending the last element 'n' to each of those gives us another b(n1) subsets, for a total of 2b(n1) subsets. Hence if n is even then, a(n) = b(n). If n is odd then, a(n) = 2b(n1). 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(n1) if n is odd.
G.f.: (2*x^3+4*x^2+2*x+2)/(4*x^4+2*x^21).
a(n) = 2a(n2) + 4a(n4).  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: A171647 A089821 A294067 * A326076 A181808 A097942
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



