Discrete Math

Subsection 6.3.1 Strong Induction

Let \(P(n)\) be a statement depending on \(n \in \mathbb{N}\text{.}\) Then, \(P(n)\) is true for all natural numbers \(n\) if,

• \(P(1)\) is true.

• For all \(k \in \mathbb{Z}\text{,}\) if \(P(1), P(2), \dots, P(k)\) is true, then \(P(k + 1)\) is true.

To contrast with strong induction, “regular” induction is sometimes called weak induction. Induction allows us to use all of the previous information, and it is also logically valid. It is called strong induction, because of the stronger hypotheses that are assumed.

In some sense, strong induction logically contains regular induction. In this way, when proving something by induction, you should always keep in mind that you can use strong induction if you need to. That is, you can assume all of the previous statements \(n = 1, 2, 3, \dots, k\) are true, not just the immediately previous case \(n = k\text{.}\)