Here is a \"proof\" by induction that any two positive integers are equal (e.g.,

Question

Here is a "proof" by induction that any two positive integers are equal (e.g., 5 = 10): First, a definition: if a and b are positive integers, define max (a, b) to be the larger of a and b if a notequalto b, and to be a if a = b. [For instance, max (3, 5) = 5, max (3, 3) = 3.] Let P (n) be the statement: "if a and b are positive integers such that max (a, b) = n, then a = b." We prove P (n) true for all n lessthanorequalto 1 by induction. [As a consequence, if a, b are any two positive integers, then a = b, since P (n) is true, where n = max (a, b).] First, P (1) is true, since if max(a, b) = 1 then a and b must both be equal to 1. Now assume P (n) is true. Let a, b be positive integers such that max (a, b) = n + 1. Then max (a - l, b - 1) = n. As we are assuming P (n), this implies that a - 1 = b - 1, hence a = b. Therefore, P (n + 1) is true. By induction, P (n) is true for all n. There must be something wrong with this "proof." Can you find the error?

Explanation / Answer

The base case has max(a,b) as 1 => a = 1 and b = 1.

When the case of P(n+1) is investigated, P(n) or a-1 and b-1 are taken into consideration.

If this process is repeated, we will have (a-2, b-2), (a-3,b-3)......until it assumingly falls to (a-(a-1), b-(b-1)) when the case (1,1) should be encountered to be true by induction.

However, if a and b are not equal, the process does not fall to (1,1) but to ((a-b+1),1) if a>b or (1,(b-a+1)) if b>a

E.g if a = 4 and b = 2

The process takes (4,2) and bases itself on (3,1) and not (1,1) as should have been the base case.

Therefore the proof is flawed.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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