Past exam of the Probability, statistics and options II course of the University of Oxford / 2010 / M / M5 / b / 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.