# Thread: Interesting question on mathematical induction

1. ## Interesting question on mathematical induction

I read this recently. I will try to define the terms carefully.
N - Set of Naturals
max(a,b) is defined in the standard way

Consider the following argument based on the Principle of Mathematical Induction.

P(n): For all a,b in N, if max(a,b)=n => a=b=n
Proof:
1. P(1) is obviously true. As, for all a,b in N, if max(a,b)=1 => a=b=1.
2. Assume P(r) is true. i.e. For all a,b in N, if max(a,b)=r => a=b=r
3. Now let there be some a,b in N such that max(a,b)=r+1. Consider a-1,b-1. Now max(a-1,b-1)=r. So under the assumption that P(r) is true, we have a-1=b-1 => a=b. Hence we have established truth of P(r+1).
And, thus by the Principle of Mathematical Induction, P(n) is true for all n in N.

So where is the goof-up? Here is my counter-argument.
If I am to pin-point the logical error in the above proof it has to be - I have not demonstrated P(r+1) is true for all a,b in N. I have only shown it to be true under the case where a>1 and b>1. (Because it is only then a-1 and b-1 can be defined). So for the case where one of then, say a, is equal to 1, I can't use P(r) as a-1 is not defined in N. And P(r+1) is obviously false when a=1. Hence the proof is flawed.

Can someone please help me in critically reviewing my counter-argument to the proposed proof? I am looking for a very specific logical flaw in the proposed proof. (And, I think I have captured it 'completely' in my counter argument).
PS: My argument becomes more evident when we look at what happens to P(2) given P(1) is true for all a,b.

Thanks.

2. Mathematical induction - Wikipedia, the free encyclopedia - specifically the part about Pólya's proof.

This is virtually the same as Pólya's induction that all horses are of the same color -- P(2) is not true. $max(1,2) = 2$, yet $1 \neq 2$. The induction step does not work here because $1-1=0 \notin \mathbb{N}$