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: Proofs for recursive sets using induction

  1. Jun 19, 2005 #1
    T* is a recursive definition, a subset of the family of ternary strings. Let T* be the smallest set such that:

    BASIS: 0 is in T*
    INDUCTION STEP: If x,y in T*, then so are x0y, 1x2 and 2 x1.

    a) Prove that if k in N, then there is no string in T* with exactly [tex]3^k +1[/tex] zeros.
    b) Prove that if k in N, then there is no string in T* that has exactly [tex] 2^(^k^+^1^) [/tex] digits.
    c) Prove that there is no string in T* whose digits sum to 97.

    I have started drawing combinations of elements in T* and am at a lost for the correlation about x0y and the zeros for a). As for b), I suspect that the answer has soemthing to do with any string being one with odd numbered digits since I can have x, x0y, ax0yb, etc. But I have no idea on how to formalise my suspicions. For part c), I fail to see the connection between the sum of T*'s digits and x,y.

    Please help, I have wrecked my brains for a week over this.
  2. jcsd
  3. Jun 20, 2005 #2
    Any suggestions?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook