Chapter 5 Induction and Recursion

Mathematical Induction

• BASIS STEP: P(1) is true
• INDUCTIVE STEP: \(\forall P(k), P(k+1)\) is true
• This completes the inductive step. By mathematical induction, ......

Strong Induction

• BASIS STEP: P(1) is true
• INDUCTIVE STEP: suppose \(P(i), 1 \le i \le n\), prove \(P(k+1)\) is true
• This completes the inductive step. By strong induction, ......

Well-ordering Property

• Every nonempty set of nonnegative integers has a least element

Example

Extra