1
$\begingroup$

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''?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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