 Solution

A time-homogeneous Markov chain on a countable state space satisfies, whenever the conditioning event has positive probability,where the last probabilities do not depend on $n$. Thus the present state contains all the past information relevant to the next transition. Time homogeneity is the convention used here, since the problem specifies a single transition matrix.