1. Not finding help here? Sign up for a free 30min 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!

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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proofs for recursive sets using induction
  1. Set Theory Proof (Replies: 4)

  2. Proof by induction (Replies: 4)

  3. Mutual Induction Proof (Replies: 3)

Loading...