Let $\left(S_{n}\right)_{n}$ be the simple symmetric random walk with $S_{0}=0 .$ Define $$ M_{n}=\left|S_{n}\right|-\sum_{k=0}^{n-1} 1_{S_{k}=0}, \quad \text { for } n \in \mathbb{N} $$ Let $\mathcal{F}_{n}=\left(S_{0}, S_{1}, \ldots, S_{n}\right)$. Prove that $\left(M_{n}\right)_{n}$ is a martingale w.r.t to $\left(\mathcal{F}_{n}\right)$
Here's what I've come up with so far:
Part 1: Here I'm proving that $E[M_n] < \infty :$ \begin{aligned} E\left[\left|M_{n}\right|\right] &=E\left[| | S_{n}|-|\sum_{k=0}^{n-1} I_{S_k=0}||\right] \\ & \leqslant E\left[\left|S_{n}\right|\right]+\sum_{k=0}^{n-1} E\left(I_{S_k=0}\right) \\ & \leqslant E\left[\left|S_{n}\right|\right]<\infty . \end{aligned}
where $E\left[\left|S_{n}\right|\right]$ is positive and hence, $(M_n)_n$ is finite.
Part 2: \begin{array}{l} E\left[M_{n+1} \mid \mathcal{F}_{n}\right]=M_{n} \\ E\left[\left|S_{n+1}\right|-\sum_{k=0}^{n} I_{S_{k}=0}\big/\mathcal{F}_{n}\right] \\ =E\left[\left|S_{n+1}\right| \big/ \mathcal{F}_{n}\right]-E\left[\sum_{k=0}^{n} I s_{k=0} \big/\mathcal{F}_{n}\right] \\ =E\left[\left|S_{n}+X_{n+1}\right| \big/ \mathcal{F}_{n}\right]-\sum_{k=0}^{n} I_{S_{k}=0} . (Here, E\left[X_{n+1}| \big/ \mathcal{F}_{n}\right]=0)\\ =\left|S_{n}\right|-\sum_{k=0}^{n} I_{S_{k}=0}=M_{n} . \end{array}
But, I think this might be incorrect as the limits in the sum is from {$k=0$ to $n$} instead of {$k=0$ to $n-1$}. Where have I gone wrong and how do I correct this?
$E(X_{n+1}/\mathcal F_n)=0$ does not tell you that $E(|S_n+X_{n+1}||\mathcal F_n)=|S_n|$.
Observe the following: $E(|S_n+X_{n+1}||\mathcal F_n)=\frac 1 2|S_n+1|+\frac 1 2|S_n-1|$ . For any non-zero integer $N$ we have $\frac 1 2|N+1|+\frac 1 2|N-1|=|N|$. When $N=0$ we get $\frac 1 2|N+1|+\frac 1 2|N-1|=1$. Since $S_n$ is an integer we can take $N=S_n$ in this. Can you finish?