# Recitation 7

In both sections, I went to through couple of questions on mathematical induction. Most of the times, we could use induction to prove a statement holds for all natural numbers. The framework for (weak) induction is as follows.

• Identify the statement $P(n)$.
• Basis step: prove $P(1)$.
• Induction step: prove that if $P(n)$ then $P(n+1)$.
• Conclusion: $\forall n\ P(n)$.

Sometimes, we use strong induction. The framework for strong induction is as follows.

• Identify the statement $P(n)$.
• Basis step: prove $P(1)$.
• Induction step: prove that if $\forall k\in\mathbb{N} \left(k < n\Rightarrow P(k)\right)$ then $P(n)$.
• Conclusion: $\forall n\ P(n)$.