Question

Suppose that the following subset T of binary strings is defined recursively: • Basis: 1 is in T • Recursively, if the binary string s is in T, then so are the strings Os, so, 181, 11s and s11 1. Carefully show why the string 011001 must be in the set T. 2. Provide an argument that shows that if s is a string in T of length n and s has an odd number of 1s, then all strings of length n+2 in T must also have an odd number of 1s.

Answer 1

1. okay let's prove it by the straight forward approach.
Start with the initial bit and use the rule to generate the desired number

=> Base is 1
=> then if 1 is in T then 10 will be in T because if s is in T then s0 will be in T
=> then if 10 is in T then 100 will be in T with the same logic
=> then if 100 is in T then 11001 will be in T because if s is in T then so is 1s1
=> then if 11001 is in T then 011001 will be in T, because if s is in T then so is 0s

so here we showed that if 1 is in T which is given, and given the recursive rules we can create the desired bit sequence which proves that 011001 is in T

2. if any string in T of length n has odd numbers of 1s then,
   possible sequences of length n+1 will be:
       0s, s0, 1s1, 11s, s11
   there is this observation that every new sequence has odd numbers of 1s because we are adding two 1s always otherwise single 0
   that concludes that every bit sequence of length n+1 will contain an odd number of 1s

In short, we know that if the sequence of length n contains an odd number of 1s then bit sequence of length n+1 in T will also contain an odd number of 1s
Now transiting this logic one step ahead, if the sequence of length n+1 in T contains an odd number of 1s then any sequence of length n+2 in T will also contain an odd number of 1s

hence proved that if the bit sequence in T of length n contains an odd number of 1s then bit sequence of length n+2 in T will also contain an odd number of 1s