Transitive closure of a finite relation If $R$ is a relation on $A$, we know that the relation 
$$T=R\cup R\circ R\cup R\circ R\circ R\cup\cdots$$
is know as the transitive closure of a relation and it is the smallest transitive relation containing $R$. It is almost trivial to prove that it is the smallest transitive relation containing $R$. But further it says that if $\vert A\vert =n$, then the transitive closure of $R$ is 
$$T=R\cup R\circ R\cup R\circ R\circ R\cup\cdots\cup (R\circ R\circ \cdots \circ R)$$
where the last composition is $n-1$ times. Now, I am finding it difficult to prove that this relation is transitive.
Please help
 A: Given any relation $R$ on $A$, the transitive closure may as well be described as the set $T$ consisting of all pairs $(a,b)\in A\times A$ such that there exists a finite sequence of elements
$$
a=a_0, a_1, a_2, \dots, a_{k-1}, a_k = b \in A
$$
with
$$
(a_0,a_1), (a_1,a_2), (a_2,a_3), \dots, (a_{k-1}, a_k) \in R.
$$
Note that when such a sequence exists for a given pair $(a,b)$, it follows that there also exists such a sequence without repetitions, since you can just remove the subsequence between the repeating elements.
Hence, you may describe the transitive closure $T$ as the set of all pairs $(a,b)$ such that there exists a non-repeating sequence in $A$ with the above property. 
Now if $|A|=n$, the maximal length of a non-repeating sequence in $A$ is $n$ and hence for the transitive closure it is enough to include only up to $(n-1)$-fold compositions of elements in $R$.
A: It suffices to prove that $R^{(n)}$ is contained in $\bigcup_{0 \leqslant i \leqslant n-1}R^{(i)}$. 
Proof. Suppose that $x \mathrel{R^{(n)}} y$. Then there is a chain $x= x_0 \mathrel{R} x_1 \mathrel{R} x_2\ \dotsm \ \mathrel{R} x_n = y$. Since $|A| = n$, two of the $x_i$'s are equal and hence the chain can be shortened. 
