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''?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Try $x=1$, $y=2$. Note that $x-1$ is not a positive integer.
answered Apr 20 '13 at 5:01
