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) S. Recursive Step: If (a, b) S, then (a + 3, b + 4) S and (a + 4, b + 3) S

a) List the elements of S produced by the basis step plus the first 3 applications of the recursive step in the definition.

b) Use strong induction on the number of applications of the recursive step of the definition to show that 7 “divides” (a+b) [or that (a+b) is a multiple of 7] when (a, b) S. That is, show that for any (a, b) S obtained by n0 applications of the recursive step of the definition of S, (a+b) = 7m for some integer m. Be sure to use strong induction.

Explanation / Answer

For a.. For the first Application we have :

(0,0) belongs to S,this implies that (0+3,0+4) belongs to Z , then (3,4),(4,3) must belongs to S

Now the rest of the applications are performed in a similar way

For B

Let P(n) be : if 7 divides an + bn , then (an,bn) belongs to S for any n >= 0.

Basis Step : when n=0 , a0=0,b0=0,3 | 0+0 and so , (0,0) belongs to S

Using the recursive definitions of S:(a0+3)+(b0+4)=0+3+0+4=7 and 7/7

Similarly(a0+4)+ (b0+3)=0+4+0+3=7 and 7/7

(a0+3,b0+4),(a0+4,b0+3) belongs to S ,, thus verifying P(n)=1

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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