Markov Chains Proof using Statistics Source: This came from "Introduction to probability" by Charles Miller Grinstead, and James Aurie Snell. It was located on page 407 and is Theorem 11.1 in the section 11.1 Introduction.
Theorem: The Theorem 11.1 states: Let $P$ be the transition matrix of a Markov chain. The $ij$th entry $P_{ij}(n)$ of the matrix $P(n)$ gives the probability that the Markov chain, starting in the state $S_i$, will be in state $S_j$, after $n$ steps. 
Proof: You start with the probability distribution $Pr(X_{k+n}=S_j | X_k = S_i)$ which can be written as a$\sum_h^\infty Pr(X_{k+n}=S_j | X_{k+n-1}=S_h)Pr(X_{k+n-1}=S_h | X_k= S_i)$. Which can be simplified down even further to the $\sum_1^n P_{jh}P_{hi}^{(n-1)}$. Which can then be simplified to the final version of $P_{ij}(n)$
Class: This is for a class called Seminar. It's a class were supposed to take the year we graduate. It is a class that we do a research essay that we then present to the class and do a set of problems every week with a new topic. (I.E. functions one week, inequalities next, then derivatives, and so on). It's supposed to be a capstone class for our degree that goes over a little bit of everything from the previous three years, but makes you think more and put things together. So we're mathematically mature, but we're not graduate level or anything. If that helps.
What I Need: I could use some help fleshing out this proof to a way that would be understandable for any college mathematics students. I'm doing it for a class and need to be able to teach anyone in my class to understand this proof, but statistics isn't my strong suit and any help would be appreciated.
 A: This proof of the Chapman-Kolmogorov Equations can be simplified without losing the essence: Consider a chain with states 1, 2, and 3, and a $3 \times 3$ transition matrix. Also consider three adjacent steps in time. To simplify notation,
let $\{X_1 = 1\} = A$, $\{X_3 = 3\} = C$, and $\{X_2 = h\} = B_h$, for $h = 1,2,3$, so that alphabetical order is time order. 
Now we wish to explore the conditional probability $P(C|A)$, that is the probability of a 2-step transition from state 1 to step 3. There are three ways that can occur, which we might diagram as $1 \rightarrow 1 \rightarrow 3$,
$1 \rightarrow 2 \rightarrow 3$ or $1 \rightarrow 3 \rightarrow 3$. Accordingly,
$$P(C|A) = \frac{P(AC)}{P(A)} = \frac{P(AB_1C) + P(AB_2C) + P(AB_3C)}{P(A)}
= \sum_h \frac{P(AB_hC)}{P(A)}.$$
Now consider the $h$th term.
$$\frac{P(AB_hC)}{P(A)} = \frac{P(C|AB_h)P(AB_h)}{P(A)} = \frac{P(C|B_h)P(AB_h)}{P(A)}
= P(B_h|A)P(C|B_h),$$
in which the second equal sign is due to the Markov property. Back in the full original notation, we now have 
$$P_{13}(2) = P\{X_3 = 3|X_1 = 1\} = \sum_h P\{X_2 =h|X_1 = 1\} P\{X_3 = 3|X_2 = h\}
= \sum_h P_{1h}P_{h3},$$
and we recognize this sum as element (1,3) of the square of the transition matrix.This expresses the 2-step transition (conditional) probability from step 1 to step 3.  Notice that a one-step transition probability from state $i$ to state $j$ can be written as $P_{ij}$ when it is considered as an element of the transition matrix or as $P_{ij}(1)$ when considered as a one-step transition probability.
Key elements illustreated in these three displayed equations are taking into account possible intermediate paths, the role of the Markov property and the relevance of matrix multiplication. Once students have absorbed these ideas, they have little difficulty expanding to a chain with more states or considering more intermediate steps.
Finally, it might be helpful to illustrate with a concrete example; perhaps use a $3 \times 3$ transition matrix with 1/2 in each diagonal element and 1/4 in all other elements. Then find the square and rewrite appropriate equations above with numbers instead of symbols. Also, such a matrix with 0's along the diagonal and 1/2 elsewhere and states 0, 1, 2 models a random walk on three elements around a circle mod 2 with movement controlled by the flip of a fair coin. For this example it is instructive to see which probabilities in the above equations are zero.
This question lies at the heart of understanding Markov chains. Even though it was proposed a while ago, I believe an answer will be of broader interest. (I'll be covering this at the beginning of a class that starts in early April '15.)
