A309874 a(n) = 2*n*Fibonacci(n-2) + (-1)^n + 1.

2, 6, 10, 20, 38, 70, 130, 234, 422, 748, 1322, 2314, 4034, 6990, 12066, 20740, 35534, 60686, 103362, 175602, 297662, 503516, 850130, 1432850, 2411138, 4051350, 6798010, 11392244, 19068662, 31882198, 53250562, 88853754, 148125014

Offset

2,1

Comments

For n >= 2, a(n) is the number of length n losing strings with a binary alphabet in the "same game".

In the "same game", winning strings are those that can be reduced to the null string by repeatedly removing an entire run of two or more consecutive symbols.

Sequence A035615 counts the winning strings of length n in a binary alphabet in the "same game".

Links

Robert Israel, Table of n, a(n) for n = 2..4764

Chris Burns and Benjamin Purcell, A note on Stephan's conjecture 77, preprint, 2005. [Cached copy]

Chris Burns and Benjamin Purcell, Counting the number of winning strings in the 1-dimensional same game, Fibonacci Quarterly, 45(3) (2007), 233-238.

Sascha Kurz, Polynomials for same game, 2001.

Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

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

Formula

a(n) = 2^n - A323844(2,n) = 2^n - A035615(n) = 2*A323812(n) for n >= 2.

G.f.: x^2*(2 + 2*x - 6*x^2 - 4*x^3 + 6*x^4 + 2*x^5)/((1-x^2)*(1-x-x^2)^2. - Robert Israel, Sep 03 2019

Example

For n=2, we have 2^2 = 4 strings of length 2 in the binary alphabet {0,1}: 00, 11, 01, and 10. Out of those strings, only 00 and 11 are winning strings in the "same game" because removing an entire run of two or more consecutive symbols gives the null string. Thus, a(2) = 2 (corresponding to the losing strings 01 and 10).
For n=3, we have 2^3 = 8 strings of length 3 in the binary alphabet {0,1}: 000, 001, 010, 100, 110, 101, 011, 111. Out of these, only the strings 000 and 111 are winning, while the rest a(2) = 6 strings are losing strings.
For n=4, we have 2^4 = 16 strings of length 4 in the binary alphabet {0,1}. From these, only 0000, 0011, 1100, 0110, 1001, and 1111 are winning strings while the rest a(4) = 16 - 6 = 10 are losing strings. (For example 0{11}0 -> 00 -> null.)
For n=8, the string 11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Maple

seq(2*n*combinat:-fibonacci(n-2) + (-1)^n + 1, n=2..100); # Robert Israel, Sep 03 2019

Mathematica

A309874[n_]:=Fibonacci[n-2]2n+(-1)^n+1; Array[A309874, 50, 2] (* Paolo Xausa, Nov 16 2023 *)

Crossrefs

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243, A323812, A323844.

Sequence in context: A096338 A198381 A309846 * A317759 A014279 A050543

Adjacent sequences: A309871 A309872 A309873 * A309875 A309876 A309877

Keyword

nonn

Author

Petros Hadjicostas, Sep 01 2019

Status

approved