When is a polynomial of an unbiased random walk a martingale? Let $X_n$, $n\geqslant 1$ be i.i.d. random variables with $\mathbb P(X_1=1)=\frac12=\mathbb P(X_1=-1)$ and define $S_n = \sum_{k=1}^n X_k$. Let  $P\in\mathbb R[x,y]$ be a polynomial in two real variables. I have read the claim

$P(S_n,n)$ is a martingale if and only if $$P(s+1,n+1) + P(s-1,n+1) = 2P(s,n).\tag 1$$

Note that $\mathbb E[|P(S_n,n)|]<\infty$ since it is a finite sum of bounded random variables, so we need only consider the martingale criteria
$$
\mathbb E[P(S_{n+1},n+1)\mid \mathcal F_n] = P(S_n,n),\tag 2
$$
where $\mathcal F_n = \sigma(X_1,\ldots,X_n)$. Claims $(1)$ and $(2)$ clearly hold for the constant polynomial $1$. If $P(S_n,n)=S_n$ then
$$
\mathbb E[S_{n+1}\mid\mathcal F_n] = \mathbb E[S_n + X_{n+1}\mid\mathcal F_n] = \mathbb E[S_n\mid\mathcal F_n] + \mathbb E[X_{n+1}\mid\mathcal F_n] = S_n + 0 = S_n,
$$
and also
$$
P(S_n+1,n+1) + P(S_n-1,n+1) = (S_n+1)+(S_n-1) = 2S_n = 2P(S_n,n),
$$
So $(1)$ and $(2)$ hold for $P(S_n,n)=S_n$. Further, we see that \begin{align}\mathbb E[S_{n+1}^2\mid\mathcal F_n] &= \mathbb E[S_n^2\mid\mathcal F_n] +2\mathbb E[S_nX_{n+1}\mid\mathcal F_n] + \mathbb E[X_{n+1}^2\mid\mathcal F_n]\\
&= S_n^2 + 2\mathbb E[X_{n+1}]S_n + \mathbb E[X_{n+1}^2]\\
&= S_n^2 + 1,
\end{align}
so setting $P(S_n,n) = S_n^2-n$, we have
$$
\mathbb E[P(S_{n+1},n+1)\mid\mathcal F_n] = S_n^2 + 1 -(n+1) = S_n^2-n = P(S_n,n),
$$
so that $S_n^2-n$ is a martingale. We verify that
\begin{align}
P(s+1,n+1)+P(s-1,n+1) &= (s+1)^2 -(n+1) + (s-1)^2 -(n+1)\\
&= 2s^2 -2(n+1) + 2\\
&= 2(s^2-n)\\
&= 2P(s,n).
\end{align}
We may continue this process by the polynomials $S_n^3-3nS_n, S_n^4-6nS_n^2+2n+3n^2$, and so on. But how do we see that $(1)$ and $(2)$ are equivalent?
 A: The conditional expectation is easily calculated since $X_{n+1}$ is independent from $\mathcal F_n$: almost surely
$$
\mathbb E[P(S_{n+1},n+1)\mid \mathcal F_n] = \mathbb E[P(S_n+X_{n+1},n+1)\mid \mathcal F_n]
$$
$$
=\frac12 P(S_n+1,n+1)+\frac12 P(S_n-1,n+1) = P(S_n,n).
$$
The last equality is what you need.
A: Note that condition (1) is equivalent to 
$$P(s,n) = \frac{P(s+1,n+1)+P(s-1,n+1)}{2}.$$
Now,
\begin{align*}
\mathbb{E}[P(S_{n+1},n+1)\mid \mathcal{F}_n] &= \sum_{s \in \mathbb{Z}}\mathbb{E}[P(S_{n+1},n+1)1\{S_{n}=s\}\mid \mathcal{F}_n]\\
&= \sum_{s \in \mathbb{Z}}1\{S_{n}=s\}\mathbb{E}[P(s+X_{n+1},n+1)]\\
&=\sum_{s \in \mathbb{Z}} 1\{S_n=s\} \frac{P(s+1,n+1)+P(s-1,n+1)}{2}\\
&=\sum_{s \in \mathbb{Z}} 1\{S_n=s\}P(s,n)\\
&=P(S_n,n).
\end{align*}
So condition (1) implies condition (2). 
For the reverse, we assume $P(S_n,n)$ is a martingale. That is, $\mathbb{E}[P(S_{n+1},n+1)\mid \mathcal{F}_n]=P(S_n,n)$. Note that for any $s \in \mathbb{Z}$ we can multiply this equation by $1\{S_n=s\}$ to get:
\begin{align*}
1\{S_n=s\}\mathbb{E}[P(S_{n+1},n+1)\mid \mathcal{F}_n] &=1\{S_n=s\}P(S_n,n)\\
1\{S_n=s\}\mathbb{E}[P(s+X_{n+1},n+1)\mid \mathcal{F}_n]&=1\{S_n=s\}P(s,n)\\
1\{S_n=s\} \frac{P(s+1,n+1)+P(s-1,n+1)}{2}&=1\{S_n=s\}P(s,n).
\end{align*}
Therefore, if $S_n=s$ occurs with positive probability, we have $\frac{P(s+1,n+1)+P(s-1,n+1)}{2}=P(s,n)$. This assumption is actually necessary. For instance, I could change the values of $P(99,1)$, $P(100,1)$, and $P(101,1)$ such that $P(99,1)+P(101,1) \neq 2 P(100,1)$ and $P(S_n,n)$ would still be a martingale since $S_1$ is far away from $100$.
