# Thread: proof by induction

1. ## proof by induction

Say I am given that $\displaystyle w^r$ means the string is spelled backwards. Ex:

$\displaystyle (hello)^R$ = olleh

The definition is:

1. w is a string of length 0 then w^R = empty set
2. w = ua, where $\displaystyle a \in \Sigma$ and $\displaystyle u \in \Sigma ^ \ast$ , is a string of length n+1>0 then $\displaystyle w^r = au^R$

prove the following:

a. $\displaystyle (xy)^R = y^Rx^R$

2. Originally Posted by EquinoX
Say I am given that $\displaystyle w^r$ means the string is spelled backwards. Ex:

$\displaystyle (hello)^R$ = olleh

The definition is:

1. w is a string of length 0 then w^R = empty set
2. w = ua, where $\displaystyle a \in \Sigma$ and $\displaystyle u \in \Sigma ^ \ast$ , is a string of length n+1>0 then $\displaystyle w^r = au^R$

prove the following:

a. $\displaystyle (xy)^R = y^Rx^R$
Use induction on the length of y. Condition 2. of the definition gives the base case, where y has length 1. If y has length n+1 then y=za, where z has length n. Use the inductive hypothesis to show that $\displaystyle (xy)^r = (xza)^r = a(xz)^r = \ldots$ (you take it from there).

Originally Posted by EquinoX
nobody are willing to help me?
If you post a query at 5 a.m. (UK time), don't get ratty if I don't reply by 7 a.m.

3. well, actually I actually I already got to that part and that's the point where I am stuck at...

4. Originally Posted by EquinoX
well, actually I actually I already got to that part and that's the point where I am stuck at...
$\displaystyle (xy)^r = (xza)^r = a(xz)^r$
$\displaystyle {\color{white}(xy)^r = (xza)^r} = az^r x^r$ (by the inductive hypothesis)
$\displaystyle {\color{white}(xy)^r = (xza)^r} = (za)^r x^r$ (by 2.)
$\displaystyle {\color{white}(xy)^r = (xza)^r} = y^r x^r$.

That's the inductive step.

5. what if it's $\displaystyle (w^R)^R = w$

I think I am supposed to use the answer from the previous part to answer this right?

6. can anyone give me some hints?

7. Hello,

Use the induction. If $\displaystyle w=xa$ where $\displaystyle a\in\Sigma,\, (x^R)^R=x$, the inductive step is like this:
$\displaystyle (w^R)^R=((xa)^R)^R=(a^Rx^R)^R=(ax^R)^R=(x^R)^Ra^R= xa=w$.

Bye.

8. Originally Posted by Opalg
$\displaystyle (xy)^r = (xza)^r = a(xz)^r$
$\displaystyle {\color{white}(xy)^r = (xza)^r} = az^r x^r$ (by the inductive hypothesis)
$\displaystyle {\color{white}(xy)^r = (xza)^r} = (za)^r x^r$ (by 2.)
$\displaystyle {\color{white}(xy)^r = (xza)^r} = y^r x^r$.

That's the inductive step.

Hmm.. I am asked to do this using the answer from part a. Not really sure if your answer really uses of the techniques in part a..

9. Originally Posted by wisterville
Hello,

Use the induction. If $\displaystyle w=xa$ where $\displaystyle a\in\Sigma,\, (x^R)^R=x$, the inductive step is like this:
$\displaystyle (w^R)^R=((xa)^R)^R=(a^Rx^R)^R=(ax^R)^R=(x^R)^Ra^R= xa=w$.

Bye.
One thing I don't understand, you mentioned w = xa, and $\displaystyle a\in\Sigma$ so what is x here? is $\displaystyle x\in (\Sigma) ^ *$ ?? Please do correct me if I am wrong

10. Hello,

Originally Posted by EquinoX
One thing I don't understand, you mentioned w = xa, and $\displaystyle a\in\Sigma$ so what is x here? is $\displaystyle x\in (\Sigma) ^ *$ ?? Please do correct me if I am wrong
Yes, you guessed right. I gave you hints, it's up to you to make it into a rigorous proof. You should know what "a proof by induction" looks like: the base case and the inductive step (assuming that the assertion holds when the length is k-1 and prove it for k. As I wrote (x^R)^R=x, you see that I assumed that the length of x is k-1 and so on...)

Bye.

11. $\displaystyle (x^R)^R = x$, is just the inductive hypothesis that you're assuming to help you solve the induction right?

you assume that a string x with a length of n holds the property $\displaystyle (x^R)^R = x$, so therefore in your inductive proof that you show on your first post is the induction for n+1 and so on?

12. Hello,

Originally Posted by EquinoX
$\displaystyle (x^R)^R = x$, is just the inductive hypothesis that you're assuming to help you solve the induction right?

you assume that a string x with a length of n holds the property $\displaystyle (x^R)^R = x$, so therefore in your inductive proof that you show on your first post is the induction for n+1 and so on?
Yes, you got it right.

Bye.

13. Originally Posted by wisterville
Hello,

Yes, you got it right.

Bye.

one last question, what would be the base case here? Is the base case for part a and b the same? From my point of view, we break w = ua. then assume that n = 0, and therefore u is a string of length 1 and so is a. So (au)^R is equal to au^R.

Please do correct me, as that's the way I see it

14. Hello,

It seems the base case is intended to be a string of length 0. (cf. Cond.1)

a. Prove (xy)^R=y^Rx^R where the length of y is 0.
Use y=y^R=empty set.

b. Prove (w^R)^R=w where the length of w is 0.
Use w=w^R=empty set.

The base case is not exactly "the same" since you prove something different. But you use the same fact (that is, Cond.1)...

Bye.