cp's OEIS Frontend

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

%I A309874 #54 Jan 05 2025 19:51:41
%S A309874 2,6,10,20,38,70,130,234,422,748,1322,2314,4034,6990,12066,20740,
%T A309874 35534,60686,103362,175602,297662,503516,850130,1432850,2411138,
%U A309874 4051350,6798010,11392244,19068662,31882198,53250562,88853754,148125014
%N A309874 a(n) = 2*n*Fibonacci(n-2) + (-1)^n + 1.
%C A309874 For n >= 2, a(n) is the number of length n losing strings with a binary alphabet in the "same game".
%C A309874 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 A309874 Sequence A035615 counts the winning strings of length n in a binary alphabet in the "same game".
%H A309874 Robert Israel, <a href="/A309874/b309874.txt">Table of n, a(n) for n = 2..4764</a>
%H A309874 Chris Burns and Benjamin Purcell, <a href="/A035615/a035615.pdf">A note on Stephan's conjecture 77</a>, preprint, 2005. [Cached copy]
%H A309874 Chris Burns and Benjamin Purcell, <a href="https://web.archive.org/web/2024*/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 A309874 Sascha Kurz, <a href="http://www.mathe2.uni-bayreuth.de/sascha/oeis/paper/same_game.pdf">Polynomials for same game</a>, 2001.
%H A309874 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.
%H A309874 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-4,-2,2,1).
%F A309874 a(n) = 2^n - A323844(2,n) = 2^n - A035615(n) = 2*A323812(n) for n >= 2.
%F A309874 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
%e A309874 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).
%e A309874 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.
%e A309874 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.)
%e A309874 For n=8, the string 11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.
%p A309874 seq(2*n*combinat:-fibonacci(n-2) + (-1)^n + 1, n=2..100); # _Robert Israel_, Sep 03 2019
%t A309874 A309874[n_]:=Fibonacci[n-2]2n+(-1)^n+1;Array[A309874,50,2] (* _Paolo Xausa_, Nov 16 2023 *)
%Y A309874 Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243, A323812, A323844.
%K A309874 nonn,easy
%O A309874 2,1
%A A309874 _Petros Hadjicostas_, Sep 01 2019