Let S be the subset of the set of ordered pairs of integers defined recursively by
Basis step: (0, 0) ∈ S.
Recursive step: If (a, b) ∈ S, then (a, b + 1) ∈ S, (a + 1, b + 1) ∈ S, and (a + 2, b + 1) ∈ S.
a) List the elements of S produced by the first four applications of the recursive definition.
b) Use strong induction on the number of applications of the recursive step of the definition to show that a ≤ 2b whenever (a, b) ∈ S.
c) Use structural induction to show that a ≤ 2b whenever (a, b) ∈ S.