Saturday, 4 July 2015

induction - Proof on String Reverse

I'm having trouble with a proof on a string reversal if anyone could lend a hand.



Given the recursive definition of String Reverse, R:





  • $\varepsilon^R = \varepsilon$


  • $(ax)^R=x^Ra, for x\in\sum^*$




Prove that $(xa)^R=ax^R$



My first instinct was to use proof by induction.



(Base Case) $|x|=0, i.e. x=\varepsilon$




LHS: $(xa)^R=(\varepsilon a)^R=(a)^r=a$



RHS: $a\varepsilon^R=a\varepsilon=a$



So our base case holds.



(Inductive Hypothesis) Assume true for $|x|=k, k \ge 0$,



$(xa)^R=ax^R$




(Inductive Step)



This is where I am stuck, as I know I have to show for the k+1 case, I can not figure out where to go from here. Any help would be appreciated, thanks!

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...