Induction proof. Explain in detail why it’s incorrect 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.
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.
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