# Proof that the $n$-step transition matrix is the $n$th power of $\mathcal{P}$

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.

$$P(X_n \mid X_{n-1}, \dots , X_0) = P(X_n \mid X_{n-1})$$
$$P(X_n \mid X_{n-k}, X_{n-k-1}, \dots, X_0) = P(X_n \mid X_{n-k})$$