Let S be the subset of the set of ordered pairs of integers defined recursively

Question

Let S be the subset of the set of ordered pairs of integers defined recursively by Basis Step: (0, 0) elementof S Recursive Step: If (a, b) elementof S, then (a, b + 1) elementof S, (a + 1, b + 1) elementof S, and (a + 2, b + 1) elementof S. List the elements of S produced by the first four applications of the recursive definition. Enter your answers in the form (a_1, b_1), ...., (a_2, b_2), .., (a_n, b_n), in order of increasing a, without any spaces. The fourth application of the recursive step adds _____ to S.

Explanation / Answer

The set S is defined recursively. So let us carry out the recursion step by step.
It is given that basis step is (0,0) is in S.
And recursive step is if (a,b) is in S then (a,b+1),(a+1,b+1) and (a+2,b+1) is in S.

Thus first recursive step adds (0,0+1), (0+1,0+1) and (0+2,0+1) to S. Thus after application of recursive definition once we have S = {(0,0),(0,1),(1,1),(2,1)}

Now let us continue applying recursion till 4th step.

2nd Recursion.
Now there are three elements in S, thus the following new elements will get added to S
(0,0) - (0,1),(1,1),(2,1)
(0,1) - (0,1+1) = (0,2) , (0+1,1+1) = (1,2), (0+2,1+1) = (2,2)
(1,1) - (1,1+1) = (1,2) ,(1+1,1+1) = (2,2), (1+2,1+1) = (3,2)
(2,1) - (2,1+1) = (2,2) ,(2+1,1+1) = (3,2), (2+2,1+1) (4,2)
Now the new elements which will get added to S are (0,2), (1,2), (2,2), (3,2), (4,2)

Thus S becomes, S = {(0,0),(0,1),(0,2),(1,1),(1,2),(2,1), (2,2), (3,2), (4,2)}.

Third recursive step, notice that all the elements which recursion can produce from (0,1),(1,1) and (2,1) are already in S, so we need to focus only on new elements that is (0,2),(1,2), (2,2), (3,2) and (4,2). Anyway we verify this claim below
(0,0) - (0,1),(1,1),(2,1)
(0,1) - (0,2), (1,2), (2,2)
(1,1) - (1,2), (2,2), (3,2)
(2,1) - (2,2), (3,2), (4,2)
(0,2) - (0,3), (1,3), (2,3)
(1,2) - (1,3), (2,3),(3,3)
(2,2) - (2,3),(3,3),(4,3)
(3,2) - (3,3),(4,3),(5,3)
(4,2) - (4,3),(5,3),(6,3)
Thus the new elements produced at 3rd step are (0,3), (1,3), (2,3),(3,3),(4,3),(5,3),(6,3).
S = {(0,0),(0,1),(0,2),(0,3),(1,1),(1,2),(1,3),(2,1), (2,2),(2,3), (3,2),(3,3) (4,2),(4,3),(5,3),(6,3)}
Looking at the patterns above we may directly construct the numbers which will get added to S at 4th stage. We need to carry out construction only on the new elements that is (0,3), (1,3), (2,3),(3,3),(4,3),(5,3),(6,3). Now since second coordinate of each element is 3 and recursion adds 1 to second coordinate all elements which will get added in this step will have the form (x,4). The first coordinated are obtained by adding 0, 1 or 2 to first coordinate. The first coordinate ranges from 0 to 6. Thus when we add 0, 1 or 2 to it we shall end up with 0 to 8.

Thus at 4 th step (0,4), (1,4), (2,4),(3,4),(4,4),(5,4),(6,4),(7,4) and (8,4) gets added to S.

Thus S after 4th recursion is {(0,0),(0,1),(0,2),(0,3),(0,4),(1,1),(1,2),(1,3),(1,4),(2,1), (2,2),(2,3),(2,4), (3,2),(3,3),(3,4), (4,2),(4,3),(4,4),(5,3),(5,4),(6,3),(6,4),(7,4),(8,4)}.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.