 Solution

A state $i$ is recurrent if the probability of returning to $i$ at a strictly positive time, starting at $i$, equals one. It is transient if that probability is less than one. If $i$ and $j$ communicate, choose $r,s$ with $p_{ji}(r)>0$ and $p_{ij}(s)>0$. Chapman-Kolmogorov givesIf $i$ is recurrent, summing over $n$ makes the right-hand side diverge, so the allowed recurrence criterion proves $j$ recurrent. Interchanging $i,j$ proves recurrence is shared throughout a communicating class, and therefore transience is shared too.

For the simple random walk, an odd number of steps cannot return to its starting point, andFor $p=1/2$ the return series diverges like $\sum n^{-1/2}$, proving recurrence. For $0<p<1$, $p\ne 1/2$, its tail is bounded by a convergent geometric series since $4p(1-p)<1$, proving transience. At $p=0$ or $1$ the walk is deterministic and never returns. Translation invariance transfers the conclusion to every state. Thus recurrence holds exactly when $p=1/2$.