to prove $(R\circ S)^*\circ R = R\circ (S\circ R)^*$

Question

For 2 relations $R$ and $S$, need to prove is

(1) $(R \circ S)^n \circ R = R\circ (S\circ R)^n$ for all $n \ge 0$

(2) $(R\circ S)^*\circ R = R\circ (S\circ R)^*$

My Work:

I was able to prove (1) using Induction.

Tried (2) as below:-

As $(R\circ S)^*\circ R = \bigcup\limits_{n=0}^\infty (R \circ S)^n \circ R$

So proof reduces to $(R \circ S)^n \circ R= R\circ (S\circ R)^*$

Now using the (1)

$R\circ (S\circ R)^n$

From here how do I conclude that it is $= R\circ (S\circ R)^*$

Answer 1

You have almost all of the pieces:

$$\begin{align*} (R\circ S)^*\circ R&=\bigcup_{n\ge 0}\Big((R\circ S)^n\Big)\circ R\\ &=\bigcup_{n\ge 0}\Big((R\circ S)^n\circ R\Big)\\ &=\bigcup_{n\ge 0}\Big(R\circ(S\circ R)^n\Big)\;, \end{align*}$$

and I expect that you can probably finish it from there.