What is wrong with this “proof” ? “Theorem:” For every positive integer n, if x

Question

What is wrong with this “proof” ? “Theorem:” For every positive integer n, if x and y are positive integers with max(x, y) = n, then x = y. “Basis step:” Suppose that n=1. If max(x, y) = 1 and x and y are positive integers, we have x = 1 and y=1. “Inductive step:” Let k be a positive integer. Assume that whenever max(x, y) = k and x and y are positive integers, then x = y. Now let max(x, y) = k + 1, where x and y are positive integers. Then max(x – 1, y – 1) = k, so by inductive hypothesis, x – 1 = y – 1. It follows that x = y, completing the inductive step.

A. The inductive hypothesis is wrong.

B. The basis step is wrong.

C. The inductive step is wrong.

D. The basis step and inductive step are wrong

Explanation / Answer

(Note: Inductive step and the inductive hypothesis are mixed up in the question!)

max(x – 1, y – 1) = k is the wrong step as x - 1 could be 0, a non-positive integer.

Therefore inductive step is wrong.

The correct answer is C.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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