In order for a proof by mathematical induction to be valid, the basis statement must be tr...

In order for a proof by mathematical induction to be valid, the basis statement must be true for n = a and the argument of the inductive step must be correct for every integer k ≥ a. In Find the mistakes in the “proofs” by mathematical induction.

Exercise

 “Theorem:” For any integer n ≥ 1, all the numbers in a set of n numbers are equal to each other.

“Proof (by mathematical induction): It is obviously true that all the numbers in a set consisting of just one number are equal to each other, so the basis step is true. For the inductive step, let A = {a1, a2, ..., ak, ak+1} be any set of k + 1 numbers. Form two subsets each of size k:

B = {a1, a2, a3, ..., ak} and

C ={a1, a3, a4, ..., ak+1}.

(B consists of all the numbers in A except ak+1, and C consists of all the numbers in A except a2.) By inductive hypothesis, all the numbers in B equal a1 and all the numbers in C equal a1 (since both sets have only k numbers). But every number in A is in B or C, so all the numbers in A equal a1; hence all are equal to each other.”