proof using a recursive definition

Question

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?

Thanks!

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.