UPDATE:
If you can prove the following identity:
$$\sum\limits_{t=0}^p \left(\frac{{2t+1 \choose t}}{2^{2t+1}}\right)^2 \frac{1}{t+2} = -1 + \frac{(2+p)}{2^{4p+4}}{2p+3 \choose p+1}^2$$
Then this is good enough to solve this question and get my gratitude as well as the 50 point bounty. I got this identity from Mathematica. See my answer below for details.
My question relates to an infinite summation and it's very elegant closed form. The expression is the solution to a nice problem which I'll get into as well. Here is the summation:
Let:
$$a_t = \left({2t+1 \choose t} – {2t+1 \choose t-1}\right)\frac{1}{2^{2+2t}}$$
and,
$$b_t = \left({2t+2 \choose t} – {2t+2 \choose t-1}\right)\frac{1}{2^{3+2t}}$$
For the very first terms of these sequences, ${n \choose -1} = 0$ for all $n$.
And the summation:
$$S = \sum_{t=0}^{\infty} \left(1-\sum_{l=0}^{t-1}b_l\right) a_t = 1- \sum_{t=0}^{\infty} \left(\sum_{l=0}^{t-1}b_l\right) a_t = 7-\frac{20}{\pi} \tag{1}$$
I know the expression above is correct (verified with a python program), but have no idea how to prove this and would like to at least see how I might approach it.
Now, why do I care about this summation? It is the solution to the following problem:
Imagine two wealthy gamblers start tossing their own separate fair coins, winning 1\$ on heads and losing 1\$ on tails. Both start at 0\$ and have infinite bank balances. The first one wants to get to 2\$ and the second one wants to get to 3\$. What is the probability that the first one will reach his goal before the second one?
One way to solve this is to consider the probability that a gambler reaches exactly $k$ dollars for the first time on toss $n$. If he has $t$ tails, then he needs $t+k$ heads. So, $n=2t+k$ (note if k=2\$, he can only reach the target on even tosses and if k=3\$, he can only reach it on odd tosses). This probability turns out to be:
$$\left({k+2t-1 \choose t} – {k+2t-1 \choose t-1}\right) \frac{1}{2^{k+t}} \frac{1}{2^t}$$
Now, let $A_n$ be the probability that the 2\$ targeting gambler wins on toss $n$ and $A$ be the probability that he wins. Then we have $A = \bigcup\limits_{n=1}^{\infty}A_n$ and so, $P(A) = \sum\limits_{n=0}^\infty P(A_n)$. Now, for the 2\$ targeting gambler to win on the $n$th toss, two things should happen:
- He should reach his target on the $n$th toss for some even $n$.
- His competitor, the 3\$ gambler should not reach his target on any toss upto $n-1$ (since he can only reach his target on odd tosses).
Putting all of this together, you can see that the probability that the 2\$ gambler wins is given by equation (1) above. I have put together some python code that approximates $S$ by going upto a large number of tosses. A Reddit user pointed out the closed form for which he used a slightly different but related approach and Mathematica. Now, how do I prove that the summation above has the closed form mentioned $(7-\frac{20}{\pi})$?
EDIT:
Here is a short python snippet that demonstrates the summation in equation (1) above.
a_t = np.array([(comb(2*t+1,t)-comb(2*t+1,t-1))/2**(2*t+2) for t in range(500)])
b_t = np.array([(comb(2*t+2,t)-comb(2*t+2,t-1))/2**(2*t+3) for t in range(500)])
b_sum = 1-np.concatenate(([0],np.cumsum(b_t)))
s = sum(a_t*b_sum[:500])
print(7-20/np.pi-s)
Also, here is the Mathematica snippet that shows the result (thanks to @SteveKass for helping with that):
Best Answer
Let $a_t \triangleq \left( \frac{\begin{pmatrix} 2t+1 \\ t \end{pmatrix}}{2^{2t+1}} \right)^2 \frac{1}{t+2}$. We need $S_p \triangleq \sum\limits_{t=0}^p a_t$ in closed form.
First, note that $$\frac{a_{t+1}}{a_t} = \frac{t+2}{t+3} . \frac{1}{2^4} . \left( \frac{ \begin{pmatrix} 2t+3 \\ t+1 \end{pmatrix} }{ \begin{pmatrix} 2t+1 \\ t \end{pmatrix} } \right)^2 = \frac{t+2}{t+3} . \frac{1}{2^4} . \left( \frac{ (2t+3)(2t+2) }{ (t+1)(t+2) } \right)^2 = \frac{(t+3/2)^2}{(t+2)(t+3)} \tag 1$$
Using $(1)$ repeatedly starting with $a_0 = 1/8$, we get:
$$a_t = \frac{1}{8} . \frac{(3/2)^2}{2.3} . \frac{(5/2)^2}{3.4} \ldots \frac{(t+1/2)^2}{(t+1).(t+2)} \text{ for $t\geq 1$} \tag 2$$
Using $(2)$, we have
$$S_0 = a_0 = \frac{1}{8} = \frac{9}{8} - 1 = \bbox[yellow]{\frac{1}{8}.3^2 - 1}$$ $$S_1 = a_1 + a_0 = a_1 + S_0 = \frac{1}{8}.\frac{(3/2)^2}{2.3} + \frac{3^2}{8} - 1 $$ $$ = \bbox[yellow]{\frac{1}{8}.\frac{(3/2)^2}{2.3}. 5^2 -1}$$ $$S_2 = a_2 + S_1 = \frac{1}{8} . \frac{(3/2)^2}{2.3} . \frac{(5/2)^2}{3.4} + \frac{5^2}{8}.\frac{(3/2)^2}{2.3} -1 $$ $$= \bbox[yellow]{\frac{1}{8} . \frac{(3/2)^2}{2.3} . \frac{(5/2)^2}{3.4}. 7^2 - 1}$$ The general pattern we observe is (can be proved formally via induction) $$ \begin{align} S_p &= \frac{1}{8}. \frac{(3/2)^2}{2.3}. \frac{(5/2)^2}{3.4} \ldots \frac{((2p+1)/2)^2}{(p+1)(p+2)}.(2p+3)^2 -1 \\ &= \frac{1}{16}. \frac{(3/2)^2}{3^2}. \frac{(5/2)^2}{4^2} \ldots \frac{((2p+1)/2)^2}{(p+2)^2}.(2p+3)^2.(p+2) -1 \\ &= \frac{1}{2^{2p+4}}. \frac{3^2}{3^2}. \frac{5^2}{4^2} \ldots \frac{(2p+1)^2}{(p+2)^2}.(2p+3)^2.(p+2) -1 \\ &= \frac{p+2}{2^{2p+4}} \left[ \frac{3.5.7 \ldots (2p+1)(2p+3)}{2.3.4 \ldots (p+1)(p+2)}.2\right]^2 -1 \\ &= \frac{p+2}{2^{2p+4}} \left[ \frac{3.5.7 \ldots (2p+1)(2p+3)}{(p+2)!}.\frac{(p+1)! 2^{p+1}}{(p+1)! 2^{p+1}}.2\right]^2 -1 \\ &= \frac{p+2}{2^{2p+4}} \left[ \frac{(2p+3)!}{(p+2)!(p+1)!}.\frac{1}{ 2^{p}}\right]^2 -1 \\ &= \frac{p+2}{2^{4p+4}} \begin{pmatrix} 2p+3 \\ p+1 \end{pmatrix}^2 -1 \\ \end{align} $$ which is what we want.