Solution
= Solution
{c}
For $n=0$, the identity <matrix> gives the assertion. Suppose it holds at $n$. Conditioning on the state at time $n$ and using the <Markov property> gives
$$
\mathbb P(X_{n+1}=j\mid X_0=i)
=\sum_k\mathbb P(X_n=k\mid X_0=i)P_{kj}
=\sum_k(P^n)_{ik}P_{kj}=(P^{n+1})_{ij}.
$$
The nonnegative countable sum is justified by the law of total probability. Induction proves \b[the $n$-step <transition matrix> is $P^n$].