Markov chains transition identity proof

Question

Let $X = (X_{n})_{n \geq 0}$ a Markov chain proof that

$$\mathbb{P}(X_{n + 2} = j \mid X_{n} = i) = \sum_{l \in \mathcal{S}} \mathbb{P}(X_{n + 2} = j, X_{n + 1} = l \mid X_{n} = i)$$

Note: $\mathcal{S}$ denotes the state space.

Answer 1

Simple Proof without using the Markov Property:

Using the fact that $\Omega = \bigcup_{l \in \mathcal{S}} \{ X_{n + 1} = l\}$, this is a disjoint union, then

$$ \begin{align} \mathbb{P}(X_{n + 2} = j \mid X_{n} = i) &= \mathbb{P}(\{ X_{n + 2} = j \} \cap \Omega \mid X_{n} = i) \\ &= \mathbb{P}\left(\{ X_{n + 2} = j\} \cap \left[ \bigcup_{l \in \mathcal{S}} \{ X_{n + 1} = l\} \right] \mid X_{n} = i \right) \\ &= \mathbb{P}\left(\bigcup_{l \in \mathcal{S}} \left[ \{ X_{n + 1} = l\} \cap \{ X_{n + 2} = j\} \right] \mid X_{n} = i \right) \\ &= \sum_{l \in \mathcal{S}} \mathbb{P}\left( \{ X_{n + 1} = l\} \cap \{ X_{n + 2} = j\} \mid X_{n} = i \right) \\ &= \sum_{l \in \mathcal{S}} \mathbb{P}\left(X_{n + 1} = l,X_{n + 2} = j \mid X_{n} = i \right) \end{align} $$