 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: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.