# Random Walk: Proving that $1 = \sum_{m=0}^{n}P_0(S_{n-m} = 0)P_0(\tau_0 > m)$

I would appreciate a further hint for this question:

Let $$S_n$$ a random walk on $$\mathbb Z$$, with $$S_0=0$$. Let $$\tau_0 = \inf\{n>0:S_n=0\}$$, the hitting time of $$0$$. Show that $$1 = \sum_{m=0}^n P_0(S_{n-m}=0) P_0(\tau_0>m).$$ (Hint: Condition according to the last time, that the chain will visit $$0$$, before time $$n$$.)

I cannot seem to work out what I should be conditioning.

For fixed $$n \in \mathbb{N}$$ set

$$\sigma := \sup\{k \leq n; S_k = 0\}.$$

Since $$\mathbb{P}(0<\tau_0 \leq n) = \mathbb{P}(0<\sigma \leq n) = \sum_{k=1}^n \mathbb{P}(\sigma=k)$$

we have

\begin{align*} \mathbb{P}(0<\tau_0 \leq n) &= \sum_{k=1}^n \mathbb{P}(S_k=0,S_{k+1} \neq 0, \ldots,S_n\neq 0) \\ &= \sum_{k=1}^n \mathbb{P}(S_k=0,S_{k+1}-S_k \neq 0, \ldots,S_n-S_k \neq 0). \end{align*}

By the independence of the increments of the random walk this implies

$$\mathbb{P}(0<\tau_0 \leq n) = \sum_{k=1}^n \mathbb{P}(S_k=0) \underbrace{\mathbb{P}(S_{k+1}-S_k \neq 0,\ldots,S_{n}-S_k \neq 0)}_{=\mathbb{P}(\tau_0>n-k)}. \tag{1}$$

On the other hand, we clearly have

$$\mathbb{P}(\tau_0>n) = \mathbb{P}(S_0=0) \mathbb{P}(\tau_0>n-0). \tag{2}$$

Adding $$(1)$$ and $$(2)$$ we conclude that

$$\underbrace{\mathbb{P}(\tau_0>0)}_{=1} = \sum_{k=0}^n \mathbb{P}(S_k=0) \mathbb{P}(\tau_0>n-k),$$

i.e.

$$1 = \sum_{m=0}^n \mathbb{P}(S_{n-m}=0) \mathbb{P}(\tau_0>m).$$