DISCRETE MATH SOLUTION ONLY 2 Let S be the set of ordered p

DISCRETE MATH SOLUTION ONLY !!!!!

2. Let S be the set of ordered pairs of integers defined recursively by (i) (3,4) in S (ii) If(x,y) in S, then(x+7,y) in S and(x-1,y-6) in S. (iii) The only elements of S are those which are obtained from (i) by applying (ii) a finite number of times. a. [1 point] Find S0, S1, and S2. b. [1 point] Use Structural Induction to prove that if (x, y) in S, then x + y is a multiple of 7.

Solution

Given that (3,4) is in S

Then (10,4) and (2,-2) should be in
S

It follows that (17,4) and ((9,-2), (9,-2) and (1,-8) are in S

-------------------------------------

We have (3,4) and sum is divisible by 7

Next element would be (10,4) and (2, -2) sums are 14 and 0 divisible by 7

Hence true for S1

-----------------------

Assume true for any (x,y)

i.e. x+y =7n for some n in N

Then x+7+y = 7(n+1) hence multiple of 7

Similarly (x-1+y-6) = 7(n-1) a multiple of 7

Thus if true for x,y true for next set

Already true for first two

Hence proved by mathematical induction that x+y is a multiple of 7