Question

Consider the following inductive definition of an approved bit string of 0's and 1's.Foundation: The bit string 0 is an approved bit string.Constructor: If s and t are approved bit strings, then so are 1s1 and s0t.Use structural induction to show that every approved bit string consists of an odd number of 0's and an even number of 1's. Make sure to indicate what P(n) is (i.e., the predicate you are proving holds true for all natural numbers n).

Answer 1

As for every proof by induction, we start with the base case: the string '0' consists of an odd number of 0's and an even number of 1's, because there is one 0 and there are no 1s (and zero is even).

Now, if we let n represent the number of iterations, we have that the initial string '0' is the 0-th iteration. So, P(n) is the claim "the string built with the n-th iteration consist of an odd number of 0's and an even number of 1's", and we have just proven P(0).

Once the base case is proven, we can assume that all proposition from P(0) to P(n-1) are true.

We can build the n-th iteration in two ways:

CASE 1: The n-th iteration is in the form 1s1.

Since s is a string obtained at some previous iteration, we can assume that is consists of an odd number of 0's (say $s_0$) and an even number of 1's (say $s_1$). The string '1s1' has the following numbers of zeroes and ones:

• Zeroes: $s_0$
• Ones: $s_1+2$

In fact, starting from s, we only added two 1's (at the beginning and the end). So, '1s1' also has an odd number of 0's (because $s_0$ is odd) and an even number of 1's (because $s_1+2$ is the sum of two even numbers).

CASE 2: The n-th iteration is in the form s0t.

Since s and t are strings obtained at some previous iteration, we can assume that they consist of an odd number of 0's ($say s_0,\ t_0$) and an even number of 1's (say $s_1,\ t_1$).

Now, how many 0's and 1's are there in the string 's0t'?

• Zeroes: $s_0+t_0+1$
• Ones: $s_1+t_1$

In fact, starting from s and t, we only added one 0 (between the two original strings). So, 's0t' also has an odd number of 0's (because $s_0+t_0+1$ is the sum of three odd numbers, and thus odd) and an even number of 1's (because $s_1+t_1$ is the sum of two even numbers, and thus even).