Proof of Chapman Kolmogorov equation

Question

In the proof of Chapman Kolmogorov Equation

$p_{ij}^{(m+n)}=\sum_{k=0}^{\infty}p_{ik}^{(n)}p_{kj}^{(m)}$

Proof:

$p_{ij}^{(m+n)}=P[X_{m+n}=j|X_0=i]$
By the total probability it says
$P[X_{m+n}=j|X_0=i]=\sum_{k=0}^{\infty} P[{X_{m+n}=j,X_n=k |X_0=i}]$.

I don't understand how $\sum_{k=0}^{\infty} P[{X_{m+n}=j,X_n=k |X_0=i}]$ was obtained. What is $X_n=k$?

Answer 1

A simplified way to put it in words:

$P(X_{m+n} = j|X_{0} = i) $ is the probability I am at location $j$ after $m+n$ steps given I start at location i

$P(X_{m+n} = j,X_{n}=k|X_{0} = i) $ is the probability I am at location $j$ after $m+n$ steps given I start at location $i$ and am at location $k$ after $n$ steps

The summation is essentially saying, if I begin at $i$ at time 0 and end at $j$ after time $m+n$, I can do this either by being at location $0$ after time $n$ ($P(X_{m+n} = j,X_{n}=0|X_{0} = i) $) or location 1 at time $n$ ($P(X_{m+n} = j,X_{n}=1|X_{0} = i$) or location two at time $n$.....