Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that we are trying to prove that for every positive integer n, if x and y are positive integers with max(x, y) = n, then x = y. For the base case, we suppose n = 1. If max(x, y) = 1 and x and y are positive integers, we have x = y = 1. Now we let k be a positive integer, and assume that whenever max(x, y) = k and x and y are positive integers, then x = y. Let max(x, y) = k + 1, where x and y are positive integers. Then max(x - 1, y - 1) = k, so by the inductive hypothesis, x - 1 = y - 1, so x = y. What is wrong with this ``proof''?

share|improve this question

2 Answers 2

Are you familiar with the proof that all horses are the same color? Try googling that phrase, it fails in a similar (but not identical) way. Try working through the case $k=1$ of your problem, and think about what might go wrong with $x$ and $y$ when you try to apply your base case.

share|improve this answer

Try $x=1$, $y=2$. Note that $x-1$ is not a positive integer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.