Show that $M_n = X_n^2 - n$ is a martingale Suppose $X_n$ is a symmetric random walk on $\mathbb{Z}$. To show that it is a martingale I need to show
$$
\mathbb{E}[M_{n+1}|X_{0:n}] = M_n
$$
$$
\begin{align}
\mathbb{E}[M_{n+1}|X_{0:n}] &= \mathbb{E}[X_{n+1}^2 - (n+1)|X_{0:n}]\\
&= \mathbb{E}[X_{n+1}^2|X_{0:n}] - (n+1)
\end{align}
$$
I'm stuck here. 
 A: Hint: $$X_{n+1}^2 = X_n^2 + (X_{n+1}-X_n)^2 + 2X_n(X_{n+1} - X_n)$$
A: Let $(S_n)_{n\in \mathbb N}$ be a simple symmetric random walk on the integers with $S_0=k$, i.e. $S_n=k+\sum_{j=1}^{n}X_j$ where $X_j\in \{-1,1\}$ with uniform distribution.
Then $\mathbb E(S_{n+1}^2-(n+1)|\mathcal{F_n})=S_n^2+\mathbb E(X_{n+1}^2)+2S_n\mathbb E(X_{n+1})-(n+1)=S_n^2-n$
A: Write
$$X_n=\sum_{k=1}^n F_k$$
Where the $F_k$ are the "coin flip" steps ($1$ and $-1$ both with probability $1/2$)
Now $\mathbb{E}(F_i F_j)=\mathbb{E}(F_i)\mathbb{E}(F_j)=0$ iff $i \neq j$
$$\therefore \mathbb{E}(X_n^2)=\sum_{k=1}^n \mathbb{E}(F_k^2) = n$$
A: Assume that the question without the -n is a martingale. The latter is easy to prove M (n) =X^2 (n). The expectation of X^2 (n+1) given the past information up to n is E(X2n) = n because it is like a wiener process that is Normal with mean zero and variance the time  (t) then the process you have has an expectation of zero and variance of 2(....)by the use of the definition of expectation and variance
