Inductive Proof on String Inequality

Question

I'm pretty new to (and therefore bad at) inductive proofs; I'm trying to do a problem from The Formal Semantics of Programming Languages, which reads:

Using mathematical induction, show that there is no string $u$ which satisfies $au = ub$ for two distinct symbols $a$ and $b$.

Here's what I have:

---

Let $u^x$ be the string $\{u_1u_2...u_x\}$.

Proof: $$ \begin{align} P(0) & \Leftrightarrow a \neq b & \textrm{(Base Cases)} \\ P(1) & \Leftrightarrow au \neq ub \\ \\ P(m) & \Leftrightarrow au^m \neq u^mb & \textrm{(Inductive Hypothesis)}\\ & \Leftrightarrow a\{u_1u_2...u_m\} \neq \{u_1u_2...u_m\}b & \textrm{(By definition of $u^x$)} \\ \\ P(m + 1) & \Leftrightarrow au^{m+1} \neq u^{m+1}b \\ & \Leftrightarrow a\{u_1u_2...u_mu_{m+1}\} \neq \{u_1u_2...u_mu_{m+1}\}b \\ & \Leftrightarrow a\{u_1u_2...u_m\}u_{m+1} \neq \{u_1u_2...u_m\}u_{m+1}b \\ & \Leftrightarrow a u^m u_{m+1} \neq u^m u_{m+1} b \end{align} $$

We have already seen that $au^m \neq u^mb$ and that adding any one character to the string $u$ (the $P(1)$ case) will not bring equality. Therefore, induction holds.

---

I'm really not sure about this one. The $P(1)$ case seems dubious to me, as does relying on it in the final statement. Also, the final statement feels very hand-wavy. I kind of expect some kind of string-algebra to help this seem more concrete.

Thanks in advance for your thoughts! (Also, if there are any resources you can recommend on the subject of inductive proofs, I'd be more than happy to hear of them.)

Answer 1

I guess that a string is a list of symbols?

In that case your $P(1)$ is correct, because there can't be a symbol $u$ that is both an $a$ and a $b$. (if $au = ub$ then $u = b$ because the string $ub$ ends with a $b$, but $u$ must be $a$ because $au$ starts with an $a$).

The $P(m + 1)$ case is more problematic because it doesn't follow directly from the inductive hypothesis and $P(1)$ isn't much of a help.

But your reasoning could follow the following line.

We know by hypothesis that $au^m \neq u^mb$.

If we assume that adding a symbol $u_{m+1}$ could help to establish equality, we can start to add it on the left hand side. We yield $au^mu_{m+1}$. Since $u_{m+1}$ is the last symbol in the string, it must equal $b$. On the right hand side we have $u^mu_{m+1}b = u^mbb = u^mbu_{m+1}$.

Because we know that $au^m \neq u^mb$, it must be that $au^{m+1} \neq u^mbu_{m+1} = u^{m+1}b$.