Let $\xi_1,\xi_2,\ldots$ be a sequence of iid random variables, such that $$\mathbb{P}(\xi_i=1)=p\ne \frac{1}{2},\,\mathbb{P}(\xi_i=-1)=q=1-p.$$ Consider the corresponding random walk $X_n=\xi_1+\xi_2+\ldots+\xi_n$. The goal is to find all functions $f:\mathbb{Z}\to\mathbb{R}$, such that $M_n=f(S_n)$ is a martingale.
What I know is that $f_0(m)=\left(\frac{q}{p}\right)^m$ is a solution (it can be shown easily). Is it true, that $f_0$ and a constant spans the space of such functions? I will be grateful for some hints.
Thanks in advance!
Elaborating on @Did's comment, from $\mathbb E[f(\xi_1)\mid S_0=k]=f(k)$ we have $$f(k)= f(k-1)\mathbb P(\xi_1=-1)+f(k+1)\mathbb P(\xi_1=1)=q\cdot f(k-1)+p\cdot f(k+1), $$ and hence $$f(k+1) - \frac1p f(k) +\left(\frac qp\right) f(k-1)=0.$$ This recurrence relation has characteristic polynomial $$\lambda^2-\frac1p\lambda +\frac qp, $$ with roots $\lambda=1,\frac qp$. It follows that $$f(k) = c_1\left(\frac qp\right)^k + c_2, $$ where $c_1,c_2\in\mathbb R$.