Induction proof. Explain in detail why it’s incorrect [duplicate]

Can somebody give a clear explanation why this is incorrect? thank you

Theorem 1: All positive integers are equal.

Proof: We show that any two positive integers are equal, from which the result follows. We do this by induction on the maximum of the two numbers. Let $P(n)$ be the statement “if $r$ and $s$ are positive integers and $\max \{ r, s \} = n$ then $r = s$.”

Clearly $P(1)$ is true. Suppose that $P(n)$ is true and let $r$ and $s$ be positive integers whose maximum is $n + 1$. Then $\max \{ r − 1, s − 1 \} = n$. By the inductive hypothesis, $r − 1 = s − 1$ and hence $r = s$. Thus $P(n + 1)$ is true.

The result is now proved by mathematical induction.

Solution 1:

There's nothing wrong with the other answers already posted, but I'd like to step back and address a slightly broader question: if presented with this argument, how would you find the flaw?

Well, if the proof worked then it would establish P(1) and then P(2) and then P(3) and so on. If it doesn't, then one of these steps must fail. Here are two ways we can identify where it goes wrong. All of them are useful heuristics when tracking down bugs in proofs.

1. If it fails, it probably fails early. Let's look at the steps in order. P(1) is certainly correct, so what about the transition from P(1) to P(2) -- the first application of the inductive step? Let's plug in some specific numbers and see what happens: r=1,s=2 perhaps. Then r-1,s-1 are 0,1 ... and, aha, this doesn't fit our inductive hypothesis.

2. Compare doubful things against what we know is actually true. So, P(n) says that all positive integers up to n are equal. That's true for n=1 but false for n=2. So, again, this tells us to focus on n=2 and see what happens.

So, to recap, here are some general principles.

• When an inductive proof fails, it usually fails "early". So try looking at small simple cases.
• In particular, the very first actual inductive step is especially likely to be wrong. More generally, look at "edge cases".
• If you can't immediately see the flaw in the reasoning, try out a concrete example.
• Compare what the proof says should be true with what you know by other means is true. Look for the first point at which the proof jumps from something you believe is true to something you believe is false.

Solution 2:

You state that $\max(r-1, s-1)=n\implies r-1=s-1$ by the inductive hypothesis. But the inductive hypothesis requires the two numbers to be positive integers, which would fail if either of $r$ or $s$ are $1$.

Solution 3:

Becase $P(n)\Rightarrow P(n+1)$ is not true for $n=1$.

It should be true for all natural $n$.