So I have a Markov chain on the nonnegative integers such that, starting from $x$, the chain goes to $x+1$ with probability $p$, $0<p<1$, and goes to state $0$ with probability $1-p$.
I'm trying to show that this chain is recurrent namely, $\sum\limits_{n=1}^\infty P_x(T_x = n) =1$ for all $x$ in the state space. After some workings, I've worked out $P_x(T_x = n)$ to be $\sum\limits_{k=1}^{n-x} {n-x-1 \choose k-1} \cdot (1-p)^k \cdot p^{n-k}$.
Now, this is the part where I am stuck, I need to show that $\sum\limits_{n=1}^\infty (\sum\limits_{k=1}^{n-x} {n-x-1 \choose k-1} \cdot (1-p)^k \cdot p^{n-k}) =1$
It'd be great if anyone could lead me from here or even better, give a more intuitive approach.
I don't know how much you know about Markov Chains but you can simplify your problem by using the concept of irreductibility. We can notice that $$\forall (i,j) \in \mathbb{N}^2, \exists n\geq 0, \quad P(X_n=j|X_0=i)>0 $$ (i.e. we can go from any $i$ to any $j$). The chain is therefore irreductible.
A property of irreductible chains (or subchains) is that every state withing share the same properties of reccurence or transience. So now you only need to pick a single state and show it is either recurrent or transient. We'll pick state $0$.
We can see that $$ P_0(T_0 = n) = p^{n-1} (1-p)$$ because to get to $0$ starting from $0$ in exactly $n$ steps means going $i \rightarrow (i+1)$ up to state $n-1$ then going to $0$.
Therefore $T_0 \sim \mathcal{G}(1-p)$ a geometric law of parametre $(1-p)$ so $$E[T_0] = \frac{1}{1-p}<\infty$$
So state $0$ is positive recurrent, therefore it is recurrent (+irrectibility of the chain) means that $(X_n)$ is recurrent.