= Solution
For $n=0$, the conditional transition probabilities are $\delta_{ij}$, the entries of $P^0=I$; for $n=1$ the assertion is the definition of $P$. For the induction step, condition on the state at time $n$ and use the <Markov property> and <time-homogeneous Markov property>[time-homogeneity]:
$$
\mathbb P(X_{n+1}=j\mid X_0=i)
=\sum_k\mathbb P(X_n=k\mid X_0=i)p_{kj}
=\sum_k(P^n)_{ik}p_{kj}=(P^{n+1})_{ij}.
$$
The countable sum is justified by the <law of total probability>; all terms are nonnegative. Thus the formula follows for every $n$ by induction. It is the <Chapman-Kolmogorov equation> for repeated one-step transitions.
Back to article page
