Exercise 3 Let S be as in Exercise 2 and let Sprime have the

Exercise 3. Let S be as in Exercise 2 and let \"S-prime\" have the same meaning as in that exercise. Use complete induction to show that each element of S greater than or equal to 4 either is a product of S. primes or is itself S-prime. Hence the analog for S of the theorem on existence of prime factorization is true. (Suggestion: Let P(k) be the sentence \"3k + 1 is S-prime or is a product of S-primes.\" Then what atlgel Teti-13 tl: ked to prove by complete induetion is that for each k EN, P(k) is true.onEx2-Let sz you are asked to prove

Solution

Given that P(k)=3k+1 where k belongs to N
and S={1,4,7,10,...}
As given in suggestion we have to prove by Induction that p(k) is true for each k belongs to N that means prove that p(k) belongs to S.

case1: take k=1
then p(1)=3(1)+1=4 clearly p(1)=4 belongs to S.
hence p(1) is true.

case2: let p(k) be true for k=m then p(m)=3m+1 where m belongs to N
then p(m) belongs to S.

case3: Now we have to prove that p(m+1) is true that is show that
p(m+1) belongs to S
P(m+1)=3(m+1)+1
P(m+1)=3m+3+1
P(m+1)=3m+1 +3
P(m+1)=p(m) +3 {from case 2}
if you look at elements of S={1,4,7,10,...} then we find that each element is obtained by adding 3 to previous element.
then p(m)+3 will also belong to S.
Hence P(m+1) belongs to S
Hence p(m+1) is true.
So by principal of Induction, Given statement is true.