I need some help with proving the following:
Let A be a set where $\left|A\right|=n$
Need to prove that the following is a transitive relation $\bigcup_{i\in\left\{0,\ldots,n-1\right\}} R^{\left(i\right)}$
(where $R^{\left(i\right)}=R\circ R\circ\ldots\circ R$ (the relation composition i times))
Well the basis was pretty easy - I got the identity relation, but I'm stuck on the induction step. I would appriciate any help!
I wouldn't do induction. The inductive step would be annoying: you would want to take a subset $B$ of $A$ with $k$ elements, restrict the relation, deduce the appropriate union (which is a subset of the union you want) is transitive, and then leverage that into showing the union you do have is transitive, which would likely involve cases depending on whether the "extra" element shows up or not.
Let $T=\cup_{k=0}^{n-1}R^{(k)}$. Let $(a,b)$ and $(b,c)$ be elements of $T$. You want to prove that $(a,c)\in T$.
There exist $i$ and $j$ such that $(a,b)\in R^{(i)}$ and $(b,c)\in R^{(j)}$. If $i=0$ then $a=b$, so you have $(a,c)=(b,c)\in T$. If $j=0$, then $b=c$, so $(a,c)=(a,b)\in T$. Thus, we may assume that $i\gt 0$ and $j\gt 0$.
Thus, there exist $x_0,x_1,\ldots,x_i$, $y_0,y_1,\ldots,y_j$ in $A$ such that $$ a=x_0,\ x_i=b,\ (x_r,x_{r+1})\in R\\ b=y_0,\ y_{j}=c,\ (y_s,y_{s+1})\in R.$$
If you have two $x$s that are the same, we can shorten the chain that yields $(a,b)$, so we may assume that $x_0,\ldots,x_i$ are pairwise distinct. Likewise, if $y_0,\ldots,y_j$ are not pairwise distinct, we can shorten the chain, and so we may assume that they are pairwise distinct.
If $i+j\lt n$, then we can simply take the sequence $$(x_0,x_1),\ldots,(x_{i-1},x_i),(y_0,y_1),\ldots,(y_{j-1},y_j)$$ of elements of $R$, and since $x_i=b=y_0$, their composition lies in $R^{(i+j)}$, which is a subset of $T$, and equals $(x_0,y_j) = (a,c)$. Thus, $(a,c)\in T$.
If $i+j\geq n$, then you want to find some way to shorten this sequence of pairs so as to get a sequence with no more than $n-1$ steps.
Now, notice that we haven't used the fact that $|A|=n$. So perhaps that will come in useful here?