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

Question

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.

Answer 1

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.

Answer 2

The induction technique that you are going to use for this is general enough to be considered structural induction. In order to solve a more advanced induction, you usually just choose what inductive assumptions you need when they end up being needed, rather than trying to list them all out beforehand. You may also assume that you are not in the base cases. Here is a brief post explaining the assumptions of structural induction.

$$xy = yx \rightarrow (\exists z)\, x = z^i \land y = z^j$$

So visually what we are proving anything $xy = yx$ is of the form: $$\underbrace{zzz...z}_x\underbrace{zzz...z}_y = \underbrace{zzz...z}_y\underbrace{zzz...z}_x$$

The statement is already in a "constructive form". That is, we can prove it by constructing the $z$ which provides witness to the $\exists$. Your problem suggests that we try to construct the $z$ inductively. We may also assume that $x$ and $y$ are not empty, as those are the base cases.

Consider the case $|x| = |y|$. Then from the definition of string equality it follows that $xy = yx \rightarrow x_i = y_i \rightarrow x = y$. So we in this case we can witness $z = x = y$.

Otherwise, let $|x| < |y|$. Then $y$ must start with $x$ and have some trailing characters $b$: $xy = yx \rightarrow y = xb$. This tells us a lot; from it we can conclude that both $x$ and $y$ must start and end with $b$.

$$xy = yx$$ $$xxb = xbx$$ $$bx = xb$$ $$x = b \bar x b$$

Further:

$$xy = yx$$ $$b \bar x b y = y x$$ $$y = b \bar y b$$

Combined: $$xy = yx$$ $$b \bar x b b \bar y b = b \bar y b b \bar x b$$ $$\bar x b b \bar y = \bar y b b \bar x$$

We see that $\bar x$ and $\bar y$ both begin and end with $b$ as well. So inductively we see that $x = b^i$ and $y = b^j$, so we can witness $z = b$.

All that is left is the base cases for $|x| = 0 \lor |y| = 0$.