A393995 Difference between the numbers of binary words of length n with an even and with an odd number of occurrences of subword 101.

1, 2, 4, 6, 8, 12, 20, 32, 48, 72, 112, 176, 272, 416, 640, 992, 1536, 2368, 3648, 5632, 8704, 13440, 20736, 32000, 49408, 76288, 117760, 181760, 280576, 433152, 668672, 1032192, 1593344, 2459648, 3796992, 5861376, 9048064, 13967360, 21561344, 33284096, 51380224

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5302

Index entries for linear recurrences with constant coefficients, signature (2,-2,2).

Formula

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

a(n) = Sum_{k>=0} (-1)^k * A118429(n,k).

a(n) = 2 * A393945(n) - 2^n.

Example

a(5) = 12 = 22 - 10 = #{00000, 00001, 00010, 00011, 00100, 00110, 00111, 01000, 01001, 01100, 01110, 01111, 10000, 10001, 10010, 10011, 10101, 11000, 11001, 11100, 11110, 11111} - #{00101, 01010, 01011, 01101, 10100, 10110, 10111, 11010, 11011, 11101}.

Maple

b:= proc(n, t, c) option remember; `if`(n=0, c,
      b(n-1, [1, 3, 1][t], c)+b(n-1, 2, `if`(t=3, -c, c)))
    end:
a:= n-> b(n, 1$2):
seq(a(n), n=0..40);
# Alternative:
a:= n-> (<<0|1|0>, <0|0|1>, <2|-2|2>>^n.<<1, 2, 4>>)[1, 1]:
seq(a(n), n=0..40);

Mathematica

LinearRecurrence[{2, -2, 2}, {1, 2, 4}, 50] (* Paolo Xausa, Apr 07 2026 *)

Crossrefs

Cf. A000079, A118429, A393945.

Sequence in context: A379713 A323114 A362231 * A118563 A228515 A363145

Adjacent sequences: A393992 A393993 A393994 * A393996 A393997 A393998

Keyword

nonn,easy

Author

Alois P. Heinz, Apr 03 2026

Status

approved