Question

1. What is wrong with the following proof that shows all integers are equal? (Please explain which step in this proof is incorrect and why is it so.) Let P(n) be the proposition that all the numbers in any set of size n are equal.

1) Base case: P(1) is clearly true.

2) Now assume that P(n) is true. That is for any set of size n all the numbers are the same. Consider any set of n + 1 numbers, lets call them a1,a2,··· ,an+1.

3) By the induction hypothesis for the set {a1,a2,··· ,an} (the first n elements) we know that a1 = a2 = ··· = an.

4) Also using the induction hypothesis for the set {a2,a3,··· ,an+1} (the last n elements) we have a2 = a3 = ··· = an+1.

5) Combining these identities together shows that a1 = a2 = ··· = an+1.

6) This shows that P(n + 1) is true and finishes the proof by induction.

Answer 1

Step-2 and step -4 are Wrong..

In step -2 we stated that Hypothesis says that our result is true for any set of n numbers which is not true because Hypothesis always states that result true for first n number (1,2,3,....,n) not any set of n number.

There are two type of proof by induction

Weak induction-Hypothesis states that result hold for the set which contains first n numbers.

Strong induction-Hypothesis states that result hold for all the set which contains element from first n numbers.

But none of hypothHypo states that result hold for any n number because it hold for a fixed set of n number.