Proving transient and recurring states of Markov chains. I am new to this platform and also new to stochastic processes. How I pose this question may not be the right way of presenting it here but I need help and I am confident that this platform has experienced and dedicated users who will help me with my question.
I would like to show that
$$P^{(n)}(i,j) = \sum_{m=1}^{n} f^{(k)} (i,j) P^{(n-m)}(j,j)$$
And then use the result to show that if $j$ is a transient state then
$$\sum_{n=1}^\infty p^{(n)}(i,j)<\infty \ \forall i $$
Give conditions on state $i$ for which $\sum_{n=1}^{\infty} p^{(n)}(i,j) = \infty$ when $j$ is recurrent.
Thanks!
 A: In your question you are not specifying what $f^{(k)}(i,j)$ is, but I presume it stands for the hitting-time, hence $f^{(k)}(i,j) = P(T_j = k \mid X_o = i)$, where $\{T_j=k\} = \{X_o\neq j,...,X_{k-1}\neq j, X_k = j\}$.
Also, I think there is a typo in first equation you want to prove. The correct one is probably the one below (note that I will change the notation a bit to make things better looking):
$$
p^{(n)}_{i,j}=\sum^n_{m=1}f^{(m)}_{i,j}p^{(n-m)}_{j,j}
$$
Now, you can prove the equation above "argumentatively", by noting that the probability of starting on $i$ and ending on $j$ after $n$ steps is just the sum of the probability of each possible path that goes from $i$ to $j$ in $n$ steps. All possible paths are summarize in the equation above, because $f_{i,j}^{(m)}$ is the probability of hitting $j$ for the first time, then $p_{j,j}^{(n-m)}$ is the probability of going from $j$ to $j$ in $n-m$ steps, which is the number of steps left. So the above equations is just a clever way of summing the probability of all possible paths.
If the above explanation is note clear enough, we can also prove with algebra.
$$
p^{(n)}_{i,j} \overset{\small Law Tot. Prob}{=} \sum^n_{m=1}P(T_j = m, X_n = j \mid X_o =i) =
$$
$$
\sum^n_{m=1}P(T_j =m \mid X_o =i)P(X_n = j \mid X_o=i, T_j =m) =
$$
$$
= \sum^n_{m=1} P(T_j =m \mid X_o =i)P(X_n = j \mid X_o=i, X_1 \neq j, ...,X_{m-1} \neq j, X_m =j) \overset{\small Markov Prop.}{=}
$$
$$
\sum^n_{m=1}P(T_j =m \mid X_o =i)P(X_n = j \mid X_m = j)=
p^{(n)}_{i,j}=\sum^n_{m=1}f^{(m)}_{i,j}p^{(n-m)}_{j,j}
$$
