I am doing a 2-part question. Thus far, I have finished the first part, requiring me to make a recursive definition of a set "S" of all binary strings, starting with a 1. I have:

Base: 1

Recursion: S1 or S0

Restriction: nothing else in the set

Now, the next question is to show, using my recursive definition, that any element in "S" encodes a number > 0.

I know how to write this in words. I would say "Since the base case, 1, is greater than 0, then concatenating 1's and 0's to the end will only make the value larger. Thus, the encoded value will never be less than 1. However, how do I state this using my recursive definition so that's it's valid?


  • $\begingroup$ If $w$ encodes the number $x$, then $w0$ encodes $2x$ and $w1$ encodes $2x+1$. $\endgroup$ Mar 31, 2014 at 3:51

1 Answer 1


Take your recursive strings definition and append a "value" function for each part of the definition:

Base: 1 - (val(1) = 1)

Recursion: S1 (val(S1) = 2val(S)+1) or S0 (val(S0) = 2 val(S))

This usually works for any recursive definition that you want to assign additional properties or interpretions to.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .