Why Mathematical Induction is Valid

• Mathematical induction to prove that ``the proposition P(n) is true for all positive integers n'':

  we prove the following two steps:

  1. Basis step: show that P(1) is true

  2. Inductive step: show that the proposition P(k) -> P(k+1) is true, where k is an arbitrary positive integer.

  After we complete the basic step and inductive step, we proved that P(n) is true for all positive integers n

• Why Mathematical Induction is valid
  

  The validity of mathematical induction follows from the Well-Ordering Property (WOP), which is a fundamental axiom of number theory. WOP states that Every nonempty subset of the set of positive integers has a least element.

  Now we use WOP to prove that P(n) is true for all positive integers:

  • Assume that there is at least one positive integer for which P(n) is false. As a result, the set S of positive integers for which P(n) is false is nonempty.

  • Thus, by WOP, S has a least element, which will be denoted by m. Correspondingly, P(m) is false.

  • We know that m cannot be 1, because P(1) is true.

  • Because m is positive and greater than 1, m-1 is a positive integer.

  • Since m-1 is less than m, it is no in S. Therefore P(m-1) must be true.

  • Because the conditional statement P(m-1) -> P(m) is true, it must be the case that P(m) is true.

  • This is a contradiction. Hence, P(n) must be true for every positive integers n.