Let $(X_n)_{n\in \mathbb{N}}$ be a Markov chain on $\mathbb{Z}$, let $p \in \left(\frac{1}{2}, 1\right) $ and let the transition probabilities be given by $P(x,x+1) = p$, $P(x,x-1) = 1-p$. We define the function $u$ by $$u(x) = \mathbb{E} \left[\sum_{n=0}^\infty a^{X_n} : X_0 =x\right], a>0$$ I would now like to show the identity $u(x+1) = au(x)$.
I was thinking, maybe we could do the following:
$$u(x+1) = \mathbb{E} \left[\sum_{n=0}^\infty a^{X_n} : X_0 =x+1\right] = \sum_{y \in \mathbb{Z}}\mathbb{E} \left[\sum_{n=0}^\infty a^{X_n} : X_0 =x+1, X_1 = y\right]P(x+1,y)$$
Now $P(x,y)$ is only non-zero for $y=x$ or $y=x+2$, so we get $$u(x+1) = p\mathbb{E} \left[\sum_{n=0}^\infty a^{X_n} : X_0 =x+1, X_1 = x+2\right] + (1-p)\mathbb{E}\left[\sum_{n=0}^\infty a^{X_n} : X_0 =x+1, X_1 = x\right]$$ Now my first question: Can we already apply the Markov property here? The Markov property (or one variation of it) states: $$\mathbb{E}\left[f(X_{t_n}) \mid \sigma(X_{t_1}, ... , X_{t_{n-1}}) \right] = \mathbb{E}\left[f(X_{t_n}) \mid X_{t_{n-1}} \right]$$ for bounded and measurable $f$. In our above equation, we don't really have a function just in $X_{t_n}$, but rather in all the $X_i$, and also I'm not sure if the expression is even bounded, so it cannot really be applied here, right? On the other hand, intuitively speaking, if we set $X_1$ for example equal to $x+2$, then $X_2, X_3, > ... $ do not care what $X_0$ is, right? Since it's a Markov Chain. So we should have $$\mathbb{E} \left[\sum_{n=0}^\infty a^{X_n} : X_0 =x+1, X_1 = x+2\right] = a^{x+1} + \mathbb{E} \left[\sum_{n=1}^\infty a^{X_n} : X_1 = x+2\right] $$ Is that correct? Now since the transition probabilities are time-independent, it should be okay to change indices, that is $$ \mathbb{E} \left[\sum_{n=1}^\infty a^{X_n} : X_1 = x+2\right] = \mathbb{E} \left[\sum_{n=0}^\infty a^{X_n} : X_0 = x+2\right] = u(x+2)$$ Now however, when applying this to our expression for $u(x+1)$, we end up with $$u(x+1) = a^{x+1} + pu(x+2) + (1-p)u(x)$$ This is unfortunately not what we are looking for. Are my observations correct so far? What else could I try here?
Edit: I have been thinking a bit about this problem and I came up with something else, not sure if this works.
We could first consider $$u_N(x) = \mathbb{E} \left[\sum_{n=0}^N a^{X_n} : X_0 =x\right]$$ which can be explicitly computed: $$u_N(x) = \sum_{(x_1, ... , x_N) \in \mathbb{Z}^N} \left( \sum_{n=0}^N a^{x_n} \right)\mathbb{P}\left(X_0 = x, X_1 = x_1, ... , X_N = x_N \right)$$ The probability of a path is just given by the product of all one-step probabilities, so $$\mathbb{P}\left(X_0 = x, ... ,X_N = x_N \right) = P(x, x_1)\cdot ...\cdot P(x_{N-1}, x_N)$$ Hence we get $$u_N(x) = \sum_{x_N \in \mathbb{Z}} ... \sum_{x_1 \in \mathbb{Z}} P(x, x_1)\cdot ...\cdot P(x_{N-1}, x_N) \left( \sum_{n=0}^N a^{x_n} \right)$$ Now since $P(x,y) = P(x+1,y+1)$ for any $x,y \in \mathbb{Z}$, we have $$au(x) = \sum_{x_N \in \mathbb{Z}} ... \sum_{x_1 \in \mathbb{Z}} P(x, x_1)\cdot ...\cdot P(x_{N-1}, x_N) \left( \sum_{n=0}^N a^{x_n+1} \right)$$ $$ = \sum_{x_N \in \mathbb{Z}} ... \sum_{x_1 \in \mathbb{Z}} P(x+1, x_1+1)\cdot ...\cdot P(x_{N-1}+1, x_N+1) \left( \sum_{n=0}^N a^{x_n+1} \right) $$ Since the sums are going through $\mathbb{Z}$, it should be okay to replace $x_i + 1$ by $x_i$, hence we get
$$au_N(x) = \sum_{x_N \in \mathbb{Z}} ... \sum_{x_1 \in \mathbb{Z}} P(x+1, x_1)\cdot ...\cdot P(x_{N-1}, x_N) \left(a^{x+1} + \sum_{n=1}^N a^{x_n} \right)=u_N(x+1)$$ Is this correct so far?
I think you are putting too much effort into this.
Consider the Markov chain $X_{n}-1$. Then this has the same transition probabilities as your original chain (that is, $\mathbb{P} [X_{n}-1 = x' \vert X_0 - 1 = x] = \mathbb{P} [X_{n} = x' \vert X_0 = x]$), and hence
$$\mathbb{E}[a^{X_n} \vert X_{0}=x+1] = \sum_{x'} a^{x'} \mathbb{P}[X_{n} = x'\ \vert X_0 = x+1]=\sum_{x'} a^{x'} \mathbb{P}[X_{n}-1 = x'-1\ \vert X_0-1 = x]=\sum_{x'} a^{x'} \mathbb{P}[X_{n} = x'-1\ \vert X_0 = x] = \sum_{z}a^{z+1} \mathbb{P}[X_{n} = z\ \vert X_0 = x] = a\sum_{z}a^{z} \mathbb{P}[X_{n} = z\ \vert X_0 = x] = a \mathbb{E}[a^{X_n} \vert X_0 = x].$$