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,3

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

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).

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

Example

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.

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 *)

Crossrefs

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

Sequence in context: A006355 A055389 A163733 * A270925 A331964 A084202

Adjacent sequences: A198831 A198832 A198833 * A198835 A198836 A198837

Keyword

nonn,easy

Author

Paul Weisenhorn, Oct 30 2011

Status

approved