A156232 a(n) is the number of induced subgraphs with odd number of edges in the cycle graph C(n).

0, 4, 4, 16, 24, 64, 112, 256, 480, 1024, 1984, 4096, 8064, 16384, 32512, 65536, 130560, 262144, 523264, 1048576, 2095104, 4194304, 8384512, 16777216, 33546240, 67108864, 134201344, 268435456, 536838144, 1073741824, 2147418112

Offset: 2

Author

Alessandro Cosentino (cosenal(AT)gmail.com), Feb 06 2009

Keywords

• nonn

Comments

Essentially the same sequence (see A204696) appears in the Cusick-Stanica paper.

Links

• G. C. Greubel, Table of n, a(n) for n = 2..1000
• Thomas W. Cusick, and Pantelimon Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Math. 258 (2002), no. 1-3, 289-301.
• Index entries for linear recurrences with constant coefficients, signature (2, 2, -4).

Crossrefs

Cf. A000749, A032085.

Programs

Mathematica

RecurrenceTable[{a[n]== 2*a[n-1]  + 2*a[n-2] - 4*a[n-3], a[0]==0, a[1]==4, a[2]==4}, a, {n,0,50}] (* G. C. Greubel, Aug 26 2015 *)
LinearRecurrence[{2, 2, -4}, {0, 4, 4}, 40] (* Vincenzo Librandi, Aug 27 2015 *)

PARI

Vec(4*x^3*(1-x)/((1-2*x)*(1-2*x^2)) + O(x^40)) \\ Michel Marcus, Aug 26 2015

Formula

a(n) = 2^(n-1) - 2^(n/2) if n is even, 2^(n-1) otherwise.

G.f.: 4*x^3*(1-x)/((1-2*x)*(1-2*x^2)). a(n)=2*a(n-1)+2*a(n-2)-4*a(n-3). - R. J. Mathar, Feb 10 2009

E.g.f.: 2*(exp(2*x) - cosh(sqrt(2)*x)). - G. C. Greubel, Aug 26 2015

Extensions

More terms from R. J. Mathar, Feb 10 2009