T* is a recursive definition, a subset of the family of ternary strings. Let T* be the smallest set such that:(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**