We have person that starts at $x=0$ and at every step he goes left with probability $0.5$ and right with probability $0.5$. What is the probability he will arrive at $x=3$ at some time?
I got $\sum_{m=0}^{\infty}$ ${2m+3 \choose m} (\frac{1}{2})^{2m+3}$ but can't compute that
On
Using Catalan numbers, we just have to prove that: $$S=\sum_{m=0}^{+\infty}\frac{1}{(4m+2)\,4^m}\binom{2m+1}{m}=1.$$ Since: $$ \frac{1}{(2m+1)\,4^m}\binom{2m+1}{m}=\frac{1}{2\sqrt{\pi}}\cdot\frac{\Gamma(m+1/2)}{\Gamma(m+2)}$$ we have: $$\begin{eqnarray*} S &=& \frac{1}{2\sqrt{\pi}\,\Gamma(3/2)}\sum_{m=0}^{+\infty}B(3/2,m+1/2)=\frac{1}{\pi}\int_{0}^{1}\sum_{m=0}^{+\infty}(1-x)^{1/2}x^{m-1/2}\,dx\\&=&\frac{1}{\pi}\int_{0}^{1}\frac{dx}{\sqrt{x(1-x)}}=\frac{2}{\pi}\int_{0}^{1}\frac{dy}{\sqrt{1-y^2}}=\frac{2}{\pi}\int_{0}^{\pi/2}1\,d\theta=\color{red}{1},\end{eqnarray*}$$ where we used the substitution $y=\sin\theta$ in the last integral.
It is a known fact that he will get at any distance, given enough time.
It is also known that, for dimension 1 and 2, he will always get back to the origin, while in dimension $\ge 3$ he will almost surely (in the probabilistic sense of the term) never get back.
Check this page for more info (a proof would use Markov Chains): http://en.wikipedia.org/wiki/Random_walk