# Proof of Chapman Kolmogorov equation

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$?

$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$.....
• To go from $i$ at time $0$ to $j$ at time $m+n$, you must be somewhere at time $n$. – Xi'an Mar 22 '15 at 20:58