- #1
evanx
- 4
- 0
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.
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.