Solution
= Solution
At $n=0$ the transition probability is $\delta_{ij}=(P^0)_{ij}$. If the assertion holds at $n$, condition on $X_n=k$ and use the <Markov property>:
$$
P(X_{n+1}=j\mid X_0=i)=\sum_k P(X_n=k\mid X_0=i)p_{kj}=\sum_k(P^n)_{ik}p_{kj}=(P^{n+1})_{ij}.
$$
<Induction> proves $\boxed{P(X_n=j\mid X_0=i)=(P^n)_{ij}}$. These countable sums contain nonnegative terms and are justified by total probability.