Discrete 5.1 & 5.2 - Mathematical & Strong Induction

Base case (mathematical induction)

prove P(n₀)

Induction (mathematical induction)

prove ∀k∈ℕ such that k≥n₀, P(k)→P(k+1).

1. Assume induction hypothesis: P(k) for an arbitrary k∈ℕ such that k≥n₀.

2. Show P(k+1).

Base case (strong induction)

prove P(n₀) and possibly a few more base cases P(n₀+1), P(n₀+2),…,P(n₀+a)

Induction step

prove ∀k∈ℕ such that k≥n₀+a, (P(n₀)∧P(n₀ + 1)∧⋯∧P(k − 1)∧ P(k))→P(k + 1).

1. Assume induction hypothesis: P(j), for all j where n₀≤j≤ k, for an arbitrary k∈ℕ such that k≥n₀+a.

2. Show P(k+1).