1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Complete Induction

  1. Oct 3, 2012 #1
    1. The problem statement, all variables and given/known data

    Question asks to prove that all binary string that begins and ends with the same number(bit) has an even number of occurences of substrings from {0,1}

    Hint: you may find useful to combine claims about strings that start and end with different bit

    2. Relevant equations

    {0} = {} since 0 is a multiple of 2 it holds.
    {11} = {} since 0 is a multiple of 2 it holds.
    eg 010010 = (01), (10), (01) (10)

    3. The attempt at a solution

    My induction hypothesis was, for all natural number n, assume that p(j) holds for some integer j such that 0 <= j < n, that is a binary string with length j that begins and ends with the same bit has an even number of ooccurences of substrings from {0,1}

    so, let j = n - 1 and by I.H we know that p(j) holds.
    j, begins and ends with the same bit. and can be represented like so, P(j) = 2t for some integer multiple t. since 1st and last digit of j is the same, we know if n = jlast then there are no additional sets created so the equation will still be p(n) = 2t + 0;

    but if we were to add n != jlast, then there would be 1 extra subset at the end since ...01 or ....10 will take place. therefore, the equation will now be p(n) = 2t + 1; even number + odd = odd. hence we've shown that for all n, if first and last digit of string is the same, there are even number of substrings from {0,1}

    I feel like I have done too much explaining in english and not enough mathenatical proof.
    is there somewhere I went too far? help is appreciated.
    Last edited: Oct 3, 2012
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted