Results 1 to 12 of 12

Math Help - recursive definitions

  1. #1
    Junior Member
    Joined
    Jun 2007
    Posts
    40

    recursive definitions

    a. give a recursive definitions of the function ones(s), which counts the number of ones in a bit string s
    b. use structural induction to prove that ones(st) = ones (s) + ones (t)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Discrete View Post
    a. give a recursive definitions of the function ones(s), which counts the number of ones in a bit string s
    b. use structural induction to prove that ones(st) = ones (s) + ones (t)
    a)

    ones("0")=0
    ones("1")=1

    ones(s|"0")=ones(s)
    ones(s|"1")=ones(s)+1

    where | is the concatenation operator

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    Does the concatenation operator here means add? I don't really get it though
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Discrete View Post
    Does the concatenation operator here means add? I don't really get it though
    We are talking of bit strings. Contatenation adjoins one bit string to the
    other, thus "101"|"11"="10111".

    In the context of strings "add" has no sensible meaning.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    But then if you just concatenate the string how will we be able to find the ones in a string??
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Discrete View Post
    But then if you just concatenate the string how will we be able to find the ones in a string??
    Let s="100110"

    ones(s) = ones("10011"|"0") = ones("10011")

    .......... = ones("1001"|"1") = ones("1001") + 1

    .......... = ones("100"|"1") + 1 = ones("100") + 1 + 1 = ones("100") + 2

    .......... = ones("10"|"0") + 2 = ones("10") + 2

    .......... = ones("1"|"0") + 2 = ones("1") + 2 = 1 + 2 = 3

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    so the suggested algorithm here is that we start from the beginning of the string and separate a single string from the back and check if it's a one or zero, if it's a one then we add one right?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Discrete View Post
    so the suggested algorithm here is that we start from the beginning of the string and separate a single string from the back and check if it's a one or zero, if it's a one then we add one right?
    Yes
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    so what's the base case here? how do I proof part b by using structural induction??
    Last edited by Discrete; August 1st 2007 at 05:20 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Discrete View Post
    so what's the base case here? how do I proof part b by using structural induction??
    The base case is that for all bit strings s and bit strings b of length 1:

    ones(s|b) = ones(s) + ones(b)

    Then suppose it true for all bit strings s and all bit strings b of length k or less. Then:

    ones(s|b)=ones(s)+ones(b)

    and so if b'=b|"0":

    ones(s|b') = ones((s|b)|"0")=ones(s|b)+0 = ones(s)+ones(b)

    and if b*=b|"1":

    ones(s|b*) = ones((s|b)|"1")=ones(s|b)+1 = ones(s)+ones(b)+1=ones(s)+ones(b|"1")=ones(s)+ones (b*).

    Hence it true for all bit strings s and all bit strings b of length k+1 or less.

    Therefore by induction we may conclude that it is true for all bit strings s and b.

    RonL
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jun 2007
    Posts
    40
    what does b', b* means??

    so there are two base case here?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Discrete View Post
    what does b', b* means??

    so there are two base case here?
    They mean what I defined them to be b' is b concatenated with "0" and b* is b concatenated with "1" , and these are part of the inductive step.

    The base case was what I said it was:

    The base case is that for all bit strings s and bit strings b of length 1:

    ones(s|b) = ones(s) + ones(b)
    This is trivial true because of the way the recursive definition of ones is set up.

    RonL

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Recursive Definitions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 12th 2011, 04:46 AM
  2. definitions
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: March 21st 2010, 12:02 PM
  3. recursive definitions
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 25th 2009, 06:57 PM
  4. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 08:32 AM
  5. definitions
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 21st 2007, 09:34 PM

Search Tags


/mathhelpforum @mathhelpforum