SE 500 Mathematics for Software Engineering
Fall 2025
HW #10: More Mathematical Induction
Due: 5pm, Wednesday November 26

Note: Because the problems here pertain to domains that we have not treated formally (namely sets and strings), your answers are not expected to be at the same level of formality as in previous homeworks. But you should endeavor to justify every logical step that you make, in the spirit of Gries & Schneider. End of note.

Relevant to the first few problem, we define the sets Sn, n=0,1,2, ..., as follows:

S0={0,1}
Sn+1= { x,y  |  x,y ∈ Sn  :  (x+y)/2 }  (n≥0)

We then define S to be the union of all the Si's: S = {∪i  |  i≥0  :  Si}

1. Prove that, for all n≥0, Sn ⊆ Sn+1. It follows that S0 ⊆ S1 ⊆ S2 ⊆ ··· = S.

(Thus, one could view S as being the limit, as n approaches infinity, of Sn)

Hint: Expressed formally, what you are being asked to prove here is

(∀n:ℕ |: Sn ⊆ Sn+1)

Translating the body into a universal quantification (see Theorem (11.13)) and then applying Theorems (8.20) and (9.2), this becomes

(∀n:ℕ, x |: x ∈ Sn ⇒ x ∈ Sn+1)

By Metatheorem (9.16), a universal quantification is a theorem iff its body is a theorem. Which is to say that it suffices to prove

x ∈ Sn  ⇒  x ∈ Sn+1

By definition, x ∈ Sn+1 is equivalent to

(∃y,z |: y,z ∈ Sn ∧ x = (y+z)/2)

Consider the use of Theorem (9.28) here!

End of (long) hint.

2. Prove by (weak) mathematical induction on n that, for all n≥0, every member of Sn is of the form k/2n for some k satisfying 0≤k≤2n.

As a corollary, it follows that no member of S, expressed as a fraction in simplest form, has a denominator that is not a power of two.

3. Prove by (weak) mathematical induction on n that for all n≥0 and k satisfying 0≤k≤2n, k/2n ∈ Sn.

It follows from (2) and (3) that

S = { k,n  |  n≥0 ∧ 0≤k≤2n  :  k/2n}

because (2) shows inclusion from left to right, and (3) shows inclusion from right to left.

The next few problems pertain to bit strings (i.e., sequences of 0's and 1's). For a bit string x, we define #0(x) (respectively, #1(x)) to be the number of occurrences of 0 (respectively, 1) in x. Specifically, the problems pertain to "good" bit strings, which we define to be any that is either 1 or of the form 0xy, where each of x and y is itself a good bit string.

Equivalently, the set of good bit strings is the language generated by the context-free grammar G (denoted L(G)) whose lone nonterminal symbol is S and whose two productions are

S   →   1   |   0SS    (1)(2)

Consider the predicates P1 and P2, each of which maps bit strings to boolean values.

In words, x satisfies P1 iff the number of occurrences of 1 in x exceeds by exactly one the number of occurrences of 0. Meanwhile, x satisfies P2 iff every proper prefix of x contains at least as many 0's as 1's.

Note: y is a proper prefix of x if x = yz for some nonempty string z.

3. Prove by (strong) mathematical induction that P1(x) is true for every good bit string x.

4. Prove by (strong) mathematical induction that P2(x) is true for every good bit string x.

5. Prove by (strong) mathematical induction that every bit string x that truthifies both P1 and P2 is a good bit string.

Hint: For the inductive step, it suffices to show that any bit string x that is of length n>1 and satisfies both P1 and P2 is of the form 0vw, where each of v and w is a bit string satisfying both P1 and P2. End of hint.

Of course, from (3), (4), and (5) it follows that the set of good bit strings is the same as the set of bit strings satisfying both P1 and P2.

In other words,

L(G)  =  { x ∈ {0,1}*  |  P1(x) ∧ P2(x)  :  x}