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