Proofs for recursive sets using induction

[evanx]

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 $$3^k +1$$ zeros.
b) Prove that if k in N, then there is no string in T* that has exactly $$2^(^k^+^1^)$$ 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.

 

[evanx]

Any suggestions?

 

[thepatientmental]

a) To prove that there is no string in T* with exactly 3^k +1 zeros, we will use proof by induction on k.
Basis: For k = 0, there is only one string in T* with 3^k +1 zeros, which is the string "0". Therefore, the statement is true for k = 0.
Induction Step: Assume that for some k in N, there is no string in T* with exactly 3^k +1 zeros. We will prove that there is no string in T* with exactly 3^(k+1) +1 zeros.
Suppose there exists a string x in T* with exactly 3^(k+1) +1 zeros. Since x is in T*, it must have been formed by applying the induction step on some strings y and z in T*. This means that y0z, 1y2, and 2y1 are also in T*. However, the number of zeros in these strings is 3^k +2, which is not equal to 3^(k+1) +1. This contradicts our assumption that x has exactly 3^(k+1) +1 zeros. Therefore, there is no string in T* with exactly 3^(k+1) +1 zeros. By induction, we can conclude that there is no string in T* with exactly 3^k +1 zeros for any k in N.

b) To prove that there is no string in T* that has exactly 2^(k+1) digits, we will use proof by induction on k.
Basis: For k = 0, there is only one string in T* with 2^(k+1) digits, which is the string "0". Therefore, the statement is true for k = 0.
Induction Step: Assume that for some k in N, there is no string in T* with exactly 2^(k+1) digits. We will prove that there is no string in T* with exactly 2^(k+2) digits.
Suppose there exists a string x in T* with exactly 2^(k+2) digits. Since x is in T*, it must have been formed by applying the induction step on some strings y and z in T*. This means that y0z, 1y2, and 2y1 are