Why is this use of structural induction for strings incorrect?

Question

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!

Answer 1

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$.