Let $\xi_1,\xi_2,...$ be a sequence of random variables such that $\xi_i=-1$ or $\xi_i=1$ for $i=1,2,...$. Let $x(n)$ be the position of a random walk at time $n$, i.e. $x(n)=\xi_1+\xi_2+...+\xi_n$. The random walk satisfies that if $x(n)=x$, then $\Bbb E\xi_{n+1}=\frac{1}{x}$. Show $\Bbb E[x^{2k}(n)]\simeq \frac{n^k(2k+1)}{2^kk!}$ where $\simeq$ denotes equivalent infinity.
I have tried several methods, including induction but none is successful. The book gives the following hint.
Hope someone can provide some help. Thank you!
I assume that by definition $p(\xi_1=+1)=1$, such that $\mathbb E_1$ is the average with this initial value. For larger values of $n$, we have by hypothesis $$p(\xi_{n+1}=+1\;|\;\mathbf x(n)=x)=\frac12\left(1+\frac1x\right).$$ This is valid only if $\mathbf x(n)>0$, but it is easy to show by induction that it is always the case (because when $\mathbf x(n)=1$ the next step is necessarily $+1$, so $\mathbf x(n+1)=2$).
Let us use the hint $$\mathbb E_1\left[ \mathbf x^{2k}(n+1)-\mathbf x^{2k}(n)\right]= \sum_{p=0}^{2k-1}\binom{2k}p \mathbb E_1\left[\mathbf x^{2k-p}(n)\right]\;\mathbb E_1\left[\xi_{n+1}^p\;|\;\mathbf x(n)\right]. $$ If $p$ is even, then $\xi_{n+1}^p=1.$ If $p$ is odd, then $\mathbb E_1\left[\mathbf x^{2k-p}(n)\xi_{n+1}^p\;|\;\mathbf x(n)=x\right]=\mathbb E_1\left[\mathbf x^{2k-p}(n)\xi_{n+1}\;|\;\mathbf x(n)=x\right]=\frac1x\mathbb E_1\left[\mathbf x^{2k-p}(n)\;|\;\mathbf x(n)=x\right]=x^{2k-p-1}$. As a conclusion, we get $$\mathbb E_1\left[ \mathbf x^{2k}(n+1)-\mathbf x^{2k}(n)\right]= \sum_{p=0}^{k-1}\left(\binom{2k}{2p}+\binom{2k}{2p+1}\right)\mathbb E_1[\mathbf x^{2k-2p}(n)]=\sum_{p=0}^{k-1}\binom{2k+1}{2p+1}\mathbb E_1[\mathbf x^{2k-2p}(n)].$$ Therefore $$\mathbb E_1\left[\mathbf x^{2k}(n)\right]=\sum_{j=0}^{n-1} \sum_{p=0}^{k-1}\binom{2k+1}{2p+1}\mathbb E_1[\mathbf x^{2k-2p}(j)].$$ You can easily verify the induction hypothesis $\mathbb E_1[\mathbf x^{2k}(n)]\simeq \frac{(2k+1)n^k}{2^kk!}$.