Part Il: Structural Induction (20 pt.) Given the following recursive definition:
ID: 3147438 • Letter: P
Question
Part Il: Structural Induction (20 pt.) Given the following recursive definition: Let S be the subset of Z x Z defined as: Basis step: (0, 0) ES Recursive step: if (a, b) E S, then: (a, b + 1) S . (a + 2,b +1) ES 1. (5 pt.) List 5 elements of Z × Z that are in S and 5 elements of Z Z that are not in S. 2. 2b for any (a, b) E S using structural induction. Answer the following 15 pt.) Prove that a S questions a. b. c. d. e. What is the base case? Complete the basis step of the proof by showing that the base case is true. What is the inductive hypothesis? What do you need to show in the inductive step of the proof? Complete the inductive step of the proof.Explanation / Answer
1. this recursive steps starting with base case (0,0) produces set S as follow:
(0,0), (0,1),(1,1)(2,1), (0,2), (1,2),(2,2), (1,2),(2,2),(3,2), (2,3),(3,3),4,3),(0,3), (1,3),(2,3), (0,4), (1,4),
5 elements of (Z x Z) that are in S: using recursive steps of S we get for (1,2) in S we have:
(1,2), (1,3), (2,3), (3,3), and since (3,3) is in S so (3,3+1) is in S i.e. ( 3,4) so all five are in S:
(1,2), (1,3), (2,3), (3,3), ( 3,4)
5 elements in of (Z x Z) that are not in S.
we can easily say that, from above large set S.
(1,0),(2,0) , (3,0), (4,0), (5,0) are not in S but in (Z x Z)