Explain the aw in each of these proofs (they are both proving claims that are cl

Question

Explain the aw in each of these proofs (they are both proving claims that are clearly false, but what’s wrong with the proof itself?). The aw will not just be an algebra error.
a. We prove with induction that every positive integer is either a perfect square or a prime number.
Base case: 1 is a perfect square.
Inductive hypothesis: Assume for every positive integer i k, i is either a perfect square or a prime number.
Inductive step: Take k + 1. If k + 1 is prime, we’re done. If it’s not prime, it can be factored into k + 1 = pq for some factors p and q, both < k + 1. By the inductive hypothesis, both p and q are perfect squares, so write them as p = u2, q = v2. Then k + 1 = u2 ·v2 = uv·uv = (uv)2, and k + 1 is a perfect square as well.

b. We prove by strong induction that for every positive integer n, 151^n1 = 1.
Base case: 15111 = 1510 = 1. Inductive hypothesis: Assume for every positive integer i k, 151i1 = 1. Inductive step: 151^(k+11) = 151k = 151k^1151^k1/151^(k11) = 11 1 (by IH) = 1

Explanation / Answer

a)

1 is not a prime number , hence the base case fails

also, if k+1 is prime , it cannot be written as perfect square

b)

base case is wrong since 1510 is not equal to 1

151^(k+1) - 1 => 151^k .151 - 1 which cannot be written in form 151^k -1

hence it is also not satisfying induction hypothesis

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

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