Induction proof. Explain in detail why it’s incorrect

Question

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.

Answer 1

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

It should be true for all natural $n$.

Answer 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$.

Answer 3

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.

Answer 4

A very simple definition of mathematical induction can be found here

which states that it has two basic steps,defining the base case and then proving the induction step.

---

Base case: is to prove the given statement for the first element of the given set (set of positive integers in this case) "if r and s are positive integers and max{r,s}=n then r=s" for the base case, let r=s= 1 then max(1,1)=1 which is true

---

Now consider the induction step. Induction step: is to prove that, if the statement is assumed to be true for any one natural number, then it must be true for the next natural number as well. So if P(n) (which means max(r,s) = n ) is true then P(n+1) (which is max(r+1,s+1)=n+1 ) should also be true

Answer 5

I'll try a little more detailed answer. The proof's loophole is in this sentence:

Then $\max \{ r − 1, s − 1 \} = n$. By the inductive hypothesis, $r − 1 = s − 1$ and hence $r = s$.

For $P(n+1)$ we have to look at a "completely fresh set" of $r$ and $s$. We only know that $r, ~ s \in \mathbb{N}$, which doesn't mean $(r-1), ~ (s-1) \in \mathbb{N}$ as well. So your sentence considers only one (specifically (2.) below) of three different cases:

1. $r = s = 1 \\ \Rightarrow \text{This case is not relevant, because there is no } n \in \mathbb{N} \text{ with } n+1=max \left \{ r, s \right \}$
2. $r, ~ s \geq 2 \\ \Rightarrow (r-1), ~ (s-1) \geq 1 \\ \Rightarrow r, ~ s \in \mathbb{N} \\ \Rightarrow \text{You're allowed to use } P(n)$
3. $r = 1, s \neq 1$ or $r \neq 1, s = 1$

You will never be able to prove (3.). Therefore you'll never complete the induction step.