Chapman Kolmogorov Equation / Theorem

Suppose ${X_n},n=0,1,2,3,.....$ is a homogeneous Markov Chain. Then

$$P_{ij}^{m+n}=\sum_kP_{ik}^mP_{kj}^n$$

That is, the conditional probability that the Markov Chain goes from state i to state j in m+n steps is equal to the sum of the conditional probabilities of reaching an intermediary state k in m steps and from k reaching state j in n steps. That is

Proof: Consider

LHS =