%I #38 Sep 17 2019 11:12:29
%S 1,3,5,10,19,35,65,117,211,374,661,1157,2017,3495,6033,10370,17767,
%T 30343,51681,87801,148831,251758,425065,716425,1205569,2025675,
%U 3399005,5696122,9534331,15941099,26625281,44426877,74062507,123360230,205303933,341416205,567353377,942154863,1563526761
%N a(n) = n*Fibonacci(n-2) + ((-1)^n + 1)/2.
%C For n >= 2, a(n) is one-half the number of length n losing strings with a binary alphabet in the "same game".
%C 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.
%C Sequence A035615 counts the winning strings of length n in a binary alphabet in the "same game", while A309874 counts the losing strings.
%C Thus, a(n) = A309874(n)/2 for n >= 2. The reason sequence A309874 is divisible by 2 is because the complement of every winning string is also a winning string (where by "complement" we mean 0 is replaced with 1 and vice versa).
%H Chris Burns and Benjamin Purcell, <a href="/A035615/a035615.pdf">A note on Stephan's conjecture 77</a>, preprint, 2005. [Cached copy]
%H Chris Burns and Benjamin Purcell, <a href="https://www.fq.math.ca/Papers1/45-3/burns.pdf">Counting the number of winning strings in the 1-dimensional same game</a>, Fibonacci Quarterly, 45(3) (2007), 233-238.
%H Sascha Kurz, Polynomials for same game, <a href="http://www.mathe2.uni-bayreuth.de/sascha/oeis/paper/same_game.pdf">pdf</a>.
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0409509">Prove or disprove: 100 conjectures from the OEIS</a>, arXiv:math/0409509 [math.CO], 2004.
%F a(n) = A309874(n)/2 for n >= 2.
%e 11011001 is a winning string because 110{11}001 -> 11{000}1 -> {111} -> null. Its complement, 00100110 is also a winning string because 001{00}110 -> 00{111}0 -> {000} -> null.
%t Table[n Fibonacci[n-2]+((-1)^n+1)/2,{n,2,40}] (* _Harvey P. Dale_, Sep 17 2019 *)
%Y Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243, A309874, A323844.
%K nonn
%O 2,2
%A _Petros Hadjicostas_, Sep 01 2019
|