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:
- Did not show that $P(w)\Rightarrow P(wa)$. What specific part of my induction step is not formal and handwavy?
- Should have done induction on $i$ (why?). Is there a reason I cannot do structrual induction on the characters of $w$?
Thanks!