Past exam of the options II course of the University of Oxford / 2010 / M / M5 / b / 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 givesThe countable sums have nonnegative terms, so they are justified by the law of total probability. Induction proves