  The payoff in the Chow-Robbins coin-tossing game is the proportion of heads
when you stop. Knowing when to stop to maximize expectation was addressed by
Chow and Robbins(1965), who proved there exist integers ${k_n}$ such that it is
optimal to stop when heads minus tails reaches this. Finding ${k_n}$ exactly
was unsolved except for finitely many cases by computer. We show ${k_n} =
\left\lceil {\alpha \sqrt n \,\, - 1/2\,\, + \,\,\frac{{\left( { - 2\zeta ( -
1/2)} \right)\sqrt \alpha }}{{\sqrt \pi }}{n^{ - 1/4}}} \right\rceil$ for
almost all n, where $\alpha $ is the Shepp-Walker constant.This comes from our
estimate ${\beta_n} = \alpha \sqrt n \,\, - 1/2\,\, + \,\,\frac{{\left( { -
2\zeta ( - 1/2)} \right)\sqrt \alpha }}{{\sqrt \pi }}{n^{ - 1/4}} + O\left(
{{n^{ - 7/24}}} \right)$ of real numbers defined by Dvoretzky(1967) for a more
general Value function which is continuous in its first argument and easier to
analyze. An $O({n^{ - 1/4}})$ dependence was conjectured by Christensen and
Fischer(2022) from numerical evidence. Our proof uses moments involving Catalan
and Catalan triangle numbers which appear in a tree resulting from backward
induction, and a generalized backward induction principle. It was motivated by
an idea of H\"aggstr\"om and W\"astlund(2013) to use backward induction of
upper and lower Value bounds from a horizon, which they used numerically to
settle a few cases. Christensen and Fischer, with much better bounds, settled
many more cases. We use Skorohod's embedding to get simple upper and lower
bounds from the Brownian analog; our upper bound is the one found by
Christensen and Fischer in a different way. We use them first for many more
examples, but the new idea is to use them algebraically in the tree, with
feedback to get a sharper Value estimate near the border, to settle almost all
n.
