Results 1 to 14 of 14

Math Help - proof by induction

  1. #1
    Member
    Joined
    Jun 2007
    Posts
    77

    proof by induction

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

    (hello)^R = olleh

    The definition is:

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

    prove the following:

    a. (xy)^R = y^Rx^R
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by EquinoX View Post
    Say I am given that w^r means the string is spelled backwards. Ex:

    (hello)^R = olleh

    The definition is:

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

    prove the following:

    a. (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 (xy)^r = (xza)^r = a(xz)^r = \ldots (you take it from there).

    Quote Originally Posted by EquinoX View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2007
    Posts
    77
    well, actually I actually I already got to that part and that's the point where I am stuck at...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by EquinoX View Post
    well, actually I actually I already got to that part and that's the point where I am stuck at...
    (xy)^r = (xza)^r = a(xz)^r
    {\color{white}(xy)^r = (xza)^r} = az^r x^r (by the inductive hypothesis)
    {\color{white}(xy)^r = (xza)^r} = (za)^r x^r (by 2.)
    {\color{white}(xy)^r = (xza)^r} = y^r x^r.

    That's the inductive step.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2007
    Posts
    77
    what if it's  (w^R)^R = w

    I think I am supposed to use the answer from the previous part to answer this right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2007
    Posts
    77
    can anyone give me some hints?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2008
    Posts
    80
    Hello,

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

    Bye.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2007
    Posts
    77
    Quote Originally Posted by Opalg View Post
    (xy)^r = (xza)^r = a(xz)^r
    {\color{white}(xy)^r = (xza)^r} = az^r x^r (by the inductive hypothesis)
    {\color{white}(xy)^r = (xza)^r} = (za)^r x^r (by 2.)
    {\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..
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2007
    Posts
    77
    Quote Originally Posted by wisterville View Post
    Hello,

    Use the induction. If w=xa where a\in\Sigma,\, (x^R)^R=x, the inductive step is like this:
    (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 a\in\Sigma so what is x here? is x\in (\Sigma) ^ * ?? Please do correct me if I am wrong
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Aug 2008
    Posts
    80
    Hello,

    Quote Originally Posted by EquinoX View Post
    One thing I don't understand, you mentioned w = xa, and a\in\Sigma so what is x here? is 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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2007
    Posts
    77
    (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 (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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Aug 2008
    Posts
    80
    Hello,

    Quote Originally Posted by EquinoX View Post
    (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 (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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jun 2007
    Posts
    77
    Quote Originally Posted by wisterville View Post
    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
    Last edited by EquinoX; September 14th 2008 at 11:42 PM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Aug 2008
    Posts
    80
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum