A198834 Number of sequences of n coin flips that win on the last flip, if the sequence of flips ends with (0,1,1) or (1,1,1).

0, 0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset: 1

Author

Paul Weisenhorn, Oct 30 2011

Keywords

• nonn
• easy

Comments

If the sequence ends with (011) Abel wins; if it ends with (111) Kain wins.

Kain(n)=0 for n <> 3; Kain(3)=1.

Abel(n) = A128588(n-2) for n > 2.

a(n) = A006355(n-1) for n > 2.

Win probability for Abel: Sum_{n>=1} Abel(n)/2^n = 7/8.

Win probability for Kain: Kain(3)/8 = 1/8.

Mean length of the game: Sum_{n>=1} n*a(n)/2^n = 7.

Appears to be essentially the same as A163733, A118658, A055389. - R. J. Mathar, Oct 31 2011

Examples

			For n=6 the a(6)=6 solutions are (0,0,0,0,1,1), (1,0,0,0,1,1); (0,1,0,0,1,1), (1,1,0,0,1,1), (0,0,1,0,1,1), (1,0,1,0,1,1) all for Abel.
		

References

• A. Engel, Wahrscheinlichkeit und Statistik, Band 2, Klett, 1978, pages 25-26.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Tian-Xiao He, Peter J.-S. Shiue, Zihan Nie, Minghao Chen, Recursive sequences and Girard-Waring identities with applications in sequence transformation, Electronic Research Archive (2020) Vol. 28, No. 2, 1049-1062.
• Index entries for linear recurrences with constant coefficients, signature (1,1).

Crossrefs

Cf. A006355, A055389, A118658, A128588, A163733.

Programs

Maple

a(1):=0: a(2):=0: a(3):=2:
ml:=0.75: pot:=8:
for n from 4 to 100 do
  pot:=2*pot:
  a(n):=a(n-1)+a(n-2):
  ml:=ml+n*a(n)/pot:
end do:
printf("%12.8f",ml);
seq(a(n),n=1..100);

Mathematica

Join[{0, 0}, Table[2*Fibonacci[n], {n, 70}]] (* Vladimir Joseph Stephan Orlovsky, Feb 10 2012 *)
Join[{0},LinearRecurrence[{1,1},{0,2},50]] (* Vincenzo Librandi, Feb 19 2012 *)

Formula

a(n) = a(n-1) + a(n-2) for n > 3.

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

a(n) = 2*A000045(n-2). - R. J. Mathar, Jan 11 2017

E.g.f.: 2 - 2*x + 2*exp(x/2)*(3*sqrt(5)*sinh(sqrt(5)*x/2) - 5*cosh(sqrt(5)*x/2))/5. - Stefano Spezia, Feb 19 2023