Prove that if $x\in\{a,b\}^*$ and $abx=xab$, then $x = (ab)^n$ for some $n\in\Bbb N$

Question

This is an exercise in text "Computability, Complexity, and Languages" by Davis et al.:

enter image description here

I can prove it easily by mathematical induction, but this exercise appears after a section titled "Proof by Contradiction", so it is supposed to be proved by deriving a contradiction.

Following is my attempt. From condition $abx=xab$ I can say $x$ begins with and end in $ab$, so I write $x$ as $abuab$ for some string $u$. After plugging it into $abx=xab$ and cancelling $ab$, I got $abu=uab$, which seems to imply nothing contradictory. If I proceed this way by writing $u$ as $abvab$, the same equation results again and again except the variable name. Then I tried to deny the conclusion, but I have difficulty in expressing $x$ in a way easy to proceed when $x\neq(ab)^n$. Can you please give me some hint (you don't have to follow my unsuccessful attempt)? Thank you.

Answer 1

You really already have what I suspect is the intended argument; you just have to look at it properly. Assume that there is a counterexample; then there is a shortest counterexample. Your argument now shows how to get a shorter counterexample and hence a contradiction.

As far as I’m concerned this is really just another way of thinking about induction, but it is technically a proof by contradiction.