[Math] Proving that $xy = yx$ where $x$ and $y$ are both strings.

computer scienceinduction

I am to prove that the following holds for any two strings $x, y \in \lbrace 0, 1\rbrace^*$

$xy = yx$ if and only if $\exists z \in \{0,1\}^*$ and $i,j \in \mathbb N$, such that $x = z^i$ and $y = z^j$

I was given a hint that I need to use induction on $|xy|$ (the sum of the length of x and the length of y) but my induction skills are poor. I am also failing to see that connection between induction on $|xy|$ and this proof.

I am guessing that the base case would be $|xy| = 0$. This would make $x$ and $y$ both the empty string, in this case the proof holds. I'm not sure where to go from here.

Any pointers would be great.

Best Answer

Here is a sketch that should help you to write the rigorous proof.

If $|x|=|y|$ then you get immediately $x=y$ and it's over. Otherwise, you can assume without loss of generality that $|x|<|y|$.

Since they commute, you know that $x$ is a prefix of $y$, so $y=xw$ for some $w$. But now, you can write $xwx=xxw$, so $xw=wx$. You end up with the same problem for smaller words, so you can conclude by induction.