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

%I #22 Jul 04 2017 09:45:29

%S 1,2,4,8,12,24,40,80,128,256,416,832,1344,2688,4352,8704,14080,28160,

%T 45568,91136,147456,294912,477184,954368,1544192,3088384,4997120,

%U 9994240,16171008,32342016,52330496

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

%C 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.

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

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,2,0,4).

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

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

%F a(n) = 2a(n-2) + 4a(n-4). - _Charles R Greathouse IV_, Dec 13 2016

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

%o (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

%Y Cf. A279245

%K nonn,easy

%O 0,2

%A _Baris Arslan_, Dec 09 2016

%E More terms from _Charles R Greathouse IV_, Dec 13 2016

%E Edited by _Michel Marcus_, Jul 04 2017