# Why is this use of structural induction for strings incorrect?

I have some questions about why my proof is incorrect.

The problem: Show that $$(w^R)^i=(w^i)^R$$whenever $$w$$ is a string and $$i$$ is a nonnegative integer; that is, show that the $$i$$th power of the reversal of a string is the reversal of the $$i$$th power of the string.

I interpreted this as "assume $$i$$ is some integer show the theorem holds for all strings". Is there a reason that this is incorrect over "assume $$w$$ is some string show this holds for all $$i$$?"

My Solution: Proof by structural induction on the characters of $$w$$.

Base Case: $$(\lambda^i)^R=\lambda^R=\lambda$$ and $$(\lambda^R)^i=\lambda^i=\lambda$$

Induction Hypothesis: Assume for all $$w\in \Sigma^*$$ $$(w^R)^i=(w^i)^R$$

Induction Step: Show holds for arbitrary $$wa$$ where $$a\in \Sigma$$.

\begin{align} ((wa)^i)^R &= ((wa)^{i-1}(wa))^R \\ &= (wa)^R((wa)^{i-1})^R \\ &\text{ by previous theorem that (w_1w_2)^R=w_2^Rw_1^R}\\ &= (wa)^R\dotsm(wa)^R \text{ i times}. \end{align} Which by definition is the same as $$((wa)^R)^i$$ which is what we wanted to show.

Why this is wrong:

1. Did not show that $$P(w)\Rightarrow P(wa)$$. What specific part of my induction step is not formal and handwavy?
2. Should have done induction on $$i$$ (why?). Is there a reason I cannot do structrual induction on the characters of $$w$$?

Thanks!

• I'm fairly sure you are asked to prove this at a level of rigor where you don't have "..."s. Have you proved that $uu^{i-1} = u^i$ for every string $u$ and positive integer $i$ ? If so, then you don't need your "..."s. (If not, then prove this as a lemma.) Nov 8 '19 at 17:28
• You can do structural induction on $w$, but you will need to justify better why $(wa)^R((wa)^{i-1})^R = ((wa)^R)^i$. Nov 8 '19 at 17:29
• @darijgrinberg And is it true that not only will I have to use that, but I will have to use the induction hypothesis somehow? I completely ignored it in my incorrect proof. Even if I were able to do what you suggested, if I did not use the induction hypothesis it is wrong. Nov 8 '19 at 17:31
• Yes, you will need your induction hypothesis. Just make the corrections I've suggested and you'll see where it can be used. Nov 8 '19 at 17:31
• @darijgrinberg Great I believe $𝑢𝑢^{𝑖−1}=𝑢^𝑖$ is simply a consequence of the recursive definition of $w^i$ however, I am stuck on justifying why $(𝑤𝑎)^𝑅((𝑤𝑎)^{𝑖−1})^𝑅=((𝑤𝑎)^𝑅)$. My issue is that I cannot isolate a $(w^R)^i$ to apply the induction hypothesis. Could I have a hint? Nov 8 '19 at 18:03

The problem with your proof is that once you fixed the integer $$i$$ and want to prove the result by induction on the length of $$w$$, you are not allowed to use the result for $$i-1$$. By the way, $$i$$ could be equal to $$0$$. When you start to use the result for $$i-1$$, you are implicitly doing an induction on $$i$$.