I am presented with the following theorem in the context of Markov chains and stochastic systems:
The $n$-step transition matrix is the $n$th power of $\mathcal{P}$:
$$\mathcal{P}^{(n)} = P^n.$$
And the following proof is provided:
Proof: First, we show that $\mathcal{P}^{(n)} = \mathcal{P}\mathcal{P}^{(n - 1)}$. This is equivalent to showing
$$p_{ij}^{(n)} = \sum_{k \in S} p_{ik}p_{kj}^{n - 1}, \ \ \ (i, j) \in S. \tag{3}$$
The events $\{ X_1 = k \}$ with $k \in S$ partition the sample space. So if $n \ge 2$, then
$$\begin{align} p_{ij}^{(n)} &= \sum_k P(X_n = j, X_1 = k \vert X_0 = i) \\ &= \sum_k P(X_n = j \vert X_1 = k, X_0 = i) P(X_1 = k \vert X_0 = i) \\ &= \sum_k P(X_n = j \vert X_1 = k) p_{ik} \\ &= \sum_k p_{kj}^{(n - 1)} p_{ik}, \end{align}$$
Now (3) follows from the iterative argument below:
$$\mathcal{P}^{(n)} = \mathcal{P} \mathcal{P}^{(n - 1)} = \mathcal{P}(\mathcal{P} \mathcal{P}^{(n - 2)}) = \mathcal{P}^2\mathcal{P}^{(n - 2)} = \dots = \mathcal{P}^n \mathcal{P}^0 = \mathcal{P}^n$$
In going from $\sum_k P(X_n = j \vert X_1 = k, X_0 = i) P(X_1 = k \vert X_0 = i)$ to $\sum_k P(X_n = j \vert X_1 = k) p_{ik}$, why did the term $P(X_n = j \vert X_1 = k, X_0 = i)$ lose $X_0 = i$ to become $P(X_n = j \vert X_1 = k)$? I'm not sure what the reasoning is for the loss of the conditional dependence on $X_0 = i$.
I would greatly appreciate it if people would please take the time to clarify this.
