Counterintuitive Markov chain problem In class, my professor said that given a Markov chain $\{X_k\}$ it intuitively should be true that 
$P(X_{k+1} = x_{k+1} \, \mid \, X_0 = a_0, \dots, X_{k-1}= a_{k-1}) = P(X_{k+1} = x_{k+1}\, \mid \,X_{k-1}= a_{k-1})$
and asked us to prove it as an exercise. Note that the indices in the conditional only go up to $k-1$. Now, to me, this in fact seems counterintuitive and contradicting the memoryless dependence of Markov chains only on the most recent state. In any case, I have been unable to prove or disprove the statement without imposing any further assumptions on $X_k$. Can anyone resolve this?
 A: The idea is that $X_k$, whatever it is, has to be something, so you sum over it:
$$
P(X_{k+1} = x_{k+1} \mid X_0 = a_0, \dots, X_{k-1} = a_{k-1})
$$
$$
= \sum_{x_k} P(X_{k+1} = x_{k+1}, X_k=x_k \mid X_0 = a_0, \dots, X_{k-1} = a_{k-1} )
$$
$$
= \sum_{x_k} P(X_{k+1} = x_{k+1}\mid X_k=x_k, X_0 = a_0, \dots, X_{k-1} = a_{k-1} )\cdot P( X_k=x_k \mid X_0 = a_0, \dots, X_{k-1} = a_{k-1} )
$$
A: 
The "intuitive" statement is actually true for any Markov chain. More generally, for every $0\leqslant i\lt j\leqslant k$,
  $$
P(X_{j:k} = x_{j:k} \mid X_{0:i} = x_{0:i})=P(X_{j:k} = x_{j:k} \mid X_{i} = x_{i}).
$$

Let $(\ast)=P(X_{k+1} = x_{k+1} \mid X_{0:k-1} = x_{0:k-1})$.
Then $$(\ast) = \displaystyle\sum_{x}P(X_{k+1} = x_{k+1},X_k=x \mid X_{0:k-1} = x_{0:k-1})$$ by the decomposition of the event $[X_{k+1} = x_{k+1}]$ along the partition $\bigcup\limits_x[X_k=x]=\Omega$.
For every $x$, $$P(X_{k+1} = x_{k+1},X_k=x \mid X_{0:k-1}=x_{k-1}) = P(X_{k+1} = x_{k+1},X_k=x \mid X_{k-1}=x_{k-1})$$ by the Markov property at time $k-1$.
Hence $$(\ast) = \displaystyle\sum_{x}P(X_{k+1} = x_{k+1},X_k=x \mid X_{k-1}=x_{k-1})=
P(X_{k+1} = x_{k+1} \mid X_{k-1}=x_{k-1})$$ by 3. and the decomposition of the event $[X_{k+1} = x_{k+1}]$ along the partition $\bigcup\limits_x[X_k=x]=\Omega$.
