A171647 a(1) = 1; for n > 1, a(n) = 2*a(n-1) if n is even, a(n) = ((n+1)/(n-1))*a(n-1) if n is odd.

1, 2, 4, 8, 12, 24, 32, 64, 80, 160, 192, 384, 448, 896, 1024, 2048, 2304, 4608, 5120, 10240, 11264, 22528, 24576, 49152, 53248, 106496, 114688, 229376, 245760, 491520, 524288, 1048576, 1114112, 2228224, 2359296, 4718592, 4980736, 9961472

Offset: 1

Author

Gary W. Adamson, Dec 13 2009

Keywords

• nonn
• easy

Comments

a(n) is the number of subsets of {1,2,...,n} that contain exactly one odd number. For example, for n=5, a(5)=12 and the 12 subsets are {1}, {3}, {5}, {1,2}, {1,4}, {2,3}, {2,5}, {3,4}, {4,5}, {1,2,4}, {2,3,4}, {2,4,5}. - Enrique Navarrete, Dec 15 2019

2*a(n-1) is the number of subsets of {1,2,...,n} that contain exactly one even number. For example, for n=5, 2*a(4)=16 and the 16 subsets are {2}, {4}, {1,2}, {1,4}, {2,3}, {2,5}, {3,4}, {4,5}, {1,2,3}, {1,2,5}, {1,3,4}, {1,4,5}, {2,3,5}, {3,4,5}, {1,2,3,5}, {1,3,4,5}. - Enrique Navarrete, Dec 16 2019

Examples

			a(6) = 2*a(5) = 2*12 = 24;
a(7) = (8/6)*a(6) = (4/3)*24 = 32.
		

Links

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

Crossrefs

Cf. A001787, A036289 (bisections).

Cf. A016631.

Programs

Magma

[ n eq 1 select 1 else IsEven(n) select 2*Self(n-1) else ((n+1)/(n-1))*Self(n-1): n in [1..40] ];

Mathematica

a[n_] := If[ OddQ@ n, (n + 1)/(n - 1) a[n - 1] , 2 a[n - 1]]; a[1] = 1; Array[a, 38]
LinearRecurrence[{0,4,0,-4},{1,2,4,8},40] (* Harvey P. Dale, Jan 14 2015 *)

Formula

From R. J. Mathar, Dec 06 2010: (Start)

a(n) = 4*a(n-2) - 4*a(n-4).

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

a(n) = (2*n - (-1)^n+1)*2^((2*n + (-1)^n - 9)/4). - Bruno Berselli, Dec 07 2010

G.f.: G(0), where G(k) = 1 + 2*x*(k+1)/(k + 1 - x*(k+1)*(k+2)/(x*(k+2) + (k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 27 2013

Sum_{n>=1} 1/a(n) = 3*log(2) (A016631). - Amiram Eldar, Aug 27 2022