login
Numerator of the probability that Alice wins the following game: Alice and Bob take turn (Alice starts first) to gain 1 or 2 chips randomly and independently with 1/2 chance, and the first player that collects at least n chips is the winner.
1

%I #23 Aug 23 2018 03:06:37

%S 1,3,13,47,185,723,2821,11127,43825,173147,685181,2713919,10762793,

%T 42715619,169654133,674238983,2680944545,10665068907,42443750893,

%U 168973210575,672913173913,2680539263219,10680581419493,42566341729431,169678604019217,676501889994363

%N Numerator of the probability that Alice wins the following game: Alice and Bob take turn (Alice starts first) to gain 1 or 2 chips randomly and independently with 1/2 chance, and the first player that collects at least n chips is the winner.

%C The formula is proved by _Wing Hong Tony Wong_ and _Jiao Xu_, and then proved by Taoye Zhang and Ju Zhou independently.

%C The probability that Alice wins the game is a(n)/4^(n-1).

%F a(n) = (4^n + Sum_(k=1..n) 4^(n-k)*(binomial(k, n-k)+binomial(k-1, n-k))^2)/8.

%t Table[(4^n + Sum[4^(n - k)*(Binomial[k, n - k] + Binomial[k - 1, n - k])^2, {k, n}])/8, {n, 100}]

%Y A265919 provides the integer sequence of the numerator of the probability that Bob wins the game. The corresponding terms of these two sequences add up to 4^n.

%K nonn

%O 1,2

%A _Wing Hong Tony Wong_, _Jiao Xu_, Dec 18 2015