Solution
= Solution
For $n=0$, the transition probabilities are the entries of the identity $P^0$. Suppose the formula holds for $n$. Conditioning on $X_n=k$ and using the <Markov property> gives
$$
P(X_{n+1}=j\mid X_0=i)
=\sum_{k\in S}P(X_n=k\mid X_0=i)P_{kj}
=\sum_k(P^n)_{ik}P_{kj}=(P^{n+1})_{ij}.
$$
The countable sums have nonnegative terms, so they are justified by the <law of total probability>. Induction proves
$$
\boxed{P(X_n=j\mid X_0=i)=(P^n)_{ij}.}
$$