1
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ 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.) $\endgroup$ Nov 8 '19 at 17:28
  • $\begingroup$ You can do structural induction on $w$, but you will need to justify better why $(wa)^R((wa)^{i-1})^R = ((wa)^R)^i$. $\endgroup$ Nov 8 '19 at 17:29
  • $\begingroup$ @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. $\endgroup$ Nov 8 '19 at 17:31
  • $\begingroup$ Yes, you will need your induction hypothesis. Just make the corrections I've suggested and you'll see where it can be used. $\endgroup$ Nov 8 '19 at 17:31
  • $\begingroup$ @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? $\endgroup$ Nov 8 '19 at 18:03
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.