Probability of Bernoulli Trials. 
You are playing a game, in which at every stage you can either win a dollar or lose one, with probabilities $p$ and $1-p$, respectively. The game is going until you don't have any money. You start with $N_0=\$1$ in the beginning. What is the probability that after the stage $n$ you have again $N_n=\$1$ in your bank?

I can't figure it out. I tried listing possible outcomes and finding some function;
e.g, all possible outcomes from 3 stages
$\{1, 2, 3, 4\}, \{1, 2, 3, 2\}, \{1, 2, 1, 2\}, \{1, 2, 1, 0\}, \{0\}$, where $\{1, 2, 3, 4\}$ is winning all three stages, and $\{0\}$ is losing your dollar immediately.
So here there are no possible ways to be left with $\$1$, clearly there have to be an even number of stages.  I really don't know where to start.
 A: Let $T$ denote the first return to state $1$ starting from state $1$. Then $T$ is infinite if the first stage is a loss, otherwise, $T=1+S$ where $S$ is the first hitting time of $1$ starting from $2$. Likewise, starting from $2$, $S=1$ if the first stage is a loss, otherwise, $S=1+S'+S''$ where $S'$ and $S''$ are i.i.d. and distributed like $S$. In terms of generating functions $g_T(u)=E[u^T]$ and $g_S(u)=E[u^S]$, defined for every $|u|\lt1$, this yields
$$
g_T(u)=pug_S(u),\qquad g_S(u)=(1-p)u+pug_S(u)^2.
$$
This yields
$$
2pug_S(u)=1-\sqrt{1-4p(1-p)u^2}=2g_T(u).
$$
Conditioning on the value of $T$, the probability $p_n$ to be again at $1$ after $2n$ steps is such that, for every $n\geqslant1$,
$$
p_n=\sum_{k=1}^nP[T=2k]p_{n-k},
$$
with the convention that $p_0=0$. Consider the generating function
$$
h(u)=\sum_{n\geqslant0}p_nu^{2n}=1+E\left[\sum_{n\geqslant1}u^n\mathbf 1_{X_{n}=1}\right].
$$
Then, the decomposition of every $p_n$ given above yields
$$
h(u)=1+g_T(u)h(u),
$$
that is,
$$
h(u)=\frac1{1-g_T(u)}=\frac{1-\sqrt{1-4p(1-p)u^2}}{2p(1-p)u^2}.
$$
Expanding $h(u)$ in powers of $u^2$ (which is direct since it only requires to expand $\sqrt{1-s}$ in powers of $s$) allows to identify $p_n$ for every $n\geqslant1$.
A: Partial answer (it gives you a start, and maybe an addendum will follow):
$S_{n}=X_{1}+\cdots+X_{n}$ where the $X_{i}$ are iid with $P\left\{ X_{i}=1\right\} =p$
and $P\left\{ X_{i}=-1\right\} =1-p$. Denote $1-p$ by $q$. Define
$M_{n}=\min\left\{ S_{1},\ldots,S_{n}\right\} $. 
Then the problem
is to compute $P\left\{ M_{n}\geq0\wedge S_{n}=0\right\} $. As you
remarked $S_{n}=0$ implies that $n$ is even, so assume that $n=2m$
where $m$ is a non-negative integer. There are $\binom{2m}{m}$ 'routes'
to 'station' $S_{2m}=0$ and each of them has probability $p^{m}q^{m}$
to be taken, but most of these routes are forbidden by the condition
$M_{2m}\geq0$. If $s_{m}$ is the number of 'legal' routes then 

$P\left\{ M_{2m}\geq0\wedge S_{2m}=0\right\} =s_{m}p^{m}q^{m}$.

So the problem is now reduced to finding $s_{m}$.
Now a start for that:
For $n=0,1,\ldots$ and $k\in\mathbb{Z}$ define $r_{n,k}$ by:
$r_{0,0}=1$, $r_{n,k}=0$ if $k<0\vee k>n$ and $r_{n,k}=r_{n-1,k-1}+r_{n-1,k+1}$
for $n>0,k\geq0$ 
Then $r_{n,k}$ can be interpreted as the number of legal
routes to station $S_{n}=k$ so that $s_{m}=r_{2m,0}$. 
I hope (haven't
found it yet) that this recursion will lead to a closed formula.
