cp's OEIS Frontend

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

%I A279245 #27 Mar 21 2018 17:09:59
%S A279245 1,2,4,6,12,20,40,64,128,208,416,672,1344,2176,4352,7040,14080,22784,
%T A279245 45568,73728,147456,238592,477184,772096,1544192,2498560,4997120,
%U A279245 8085504,16171008,26165248,52330496,84672512,169345024,274006016,548012032,886702080
%N A279245 Number of subsets of {1, 2, 3, ..., n} that include no consecutive odd integers.
%C A279245 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).
%H A279245 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,2,0,4).
%F A279245 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).
%F A279245 G.f.: -(2*x^3+2*x^2+2*x+1)/(4*x^4+2*x^2-1). - _Alois P. Heinz_, Dec 09 2016
%F A279245 a(n) = 2a(n-2) + 4a(n-4). - _Charles R Greathouse IV_, Dec 13 2016
%e A279245 a(3)=6; the 6 subsets of {1, 2, 3} that contain no consecutive odd integers are {}, {1}, {2}, {3}, {1,2}, {2,3}.
%t A279245 LinearRecurrence[{0,2,0,4},{1,2,4,6},40] (* _Harvey P. Dale_, Mar 21 2018 *)
%o A279245 (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
%K A279245 nonn,easy
%O A279245 0,2
%A A279245 _Baris Arslan_, Dec 08 2016