How to prove "If $R$ is transitive, then $R^n$ is transitive."? I can understand $R^n$ is $R$'s subset, but I can't understand why $R^n$ is transitive,too.
I used mathematical induction:
Basis step: Let $n = 2$. If $a R^2 b$, $b R^2 c$, I need to prove $a R^2 c$. Because $a R^2 b$, it follows that there exists $x \in A$ (assume $R$ is a relation on $A$) such that $a R x$ and $x R b$. From $R$'s transitivity we can get $a R b$. WLOF, we can get $b R c$. By relation's composition, $a R^2 c$ holds.
Inductive step: Assume $R^n$ is transitive, I need to prove $R^{(n+1)}$ is also transitive. That is, I need to prove if $a R^{(n+1)} b$ and $b R^{(n+1)} c$, then $a R^{(n+1)} c$. If $a R^{(n+1)} b$, then there exists $x$ such that $a R x$ and $x R^n b$. If $b R^{(n+1)} c$, then there exists $y$ such that $b R y$ and $y R^n c$.....
I don't know how to continue.
 A: In general, $R$ is transitive iff $R \circ R \subseteq R$. From this you can prove directly:
If $R,S$ are transitive relations on the same set which commute ($R \circ S = S \circ R$), then $R \circ S$ is transitive.
By induction, if $R_1,\dotsc,R_n$ are pairwise commuting transitive relations, then $R_1 \circ \dotsc \circ R_n$ is also transitive.
A: The left part is :
if $(a,b) \in R $ and $(b,c) \in R => (a,c) \in R. $  ---1.1    
if n = 1, then $R^{n} = R^{1}$ is transitive. 
Assume $R^{n}$ is transitive, we want to prove $R^{n + 1}$ is transitive.
Because $R^{n}$ is transitive, we can know that 
if $(a,b) \in R^{n} $ and $(b,c) \in R^{n} => (a,c) \in R^{n}$ . --- 1.2
What we want is  if $(a,b) \in R^{n+1} $ and $(b,c) \in R^{n+1} => (a,c) \in R^{n+1}$ . ---1.3
By definition, $R^{n+1} = R^{n} \circ R$  --- 2.1
And if R is transitive, then $R^{n} \subseteq R$. --- 2.2
In conclusion,
if $(a,b) \in R^{n+1} $ and $(b,c) \in R^{n+1}$  
=> if $(a,m1) \in R $ and $(m1,b) \in R^{n}$ and $(b,m2) \in R$ and $(m2,c) \in R^{n}$  //use 2.1
=>  if $(a,m1) \in R $ and $(m1,b) \in R$ and $(b,m2) \in R$ and $(m2,c) \in R^{n}$  //use 2.2
=> if $(a,m2) \in R $ and $(m2,c) \in R^{n}$  // R is transitive
=> $ (a,c) \in R^{n+1} $  // use 2.1
#
So combine 1.1 and 1.2 we can prove 1.3.
A: We know: $R$ is transitive iff $R^n\subseteq R$ for $n=1,2,3,\dots.$
To prove: If $S$ is transitive, $S^n$ is also transitive for $n=1,2,3,\dots.$
Say $S$ is a relation on $A$. Suppose $S^n$ is transitive for some $n\ge1$. Let $(a,b), (b,c)$ both in $ S^{n+1}$ and $x,y\in A$, so
$$\begin{align}
(a, x)&\in S\\
(x, b)&\in S^{n}\subseteq S
\end{align}$$
and 
$$\begin{align}
(b, y)&\in S\\
(y, c)&\in S^{n}\subseteq S
\end{align},$$
now since $(a,x),(x,b),(b,y)$ are in $S,$ $(a,y)\in S,$ so by definition
$$(a,c)\in S^{n+1},$$
which should complete the induction part of the proof.
