Exercise · ZW-MATHEMATICAL-INDUCTION-009 · ★★★ Advanced
Let \(P(n)\): «\(n=n+1\)». It is proved that \(P(k)\Rightarrow P(k+1)\) by adding \(1\) to both sides. What follows?
Choose one option.
A Nothing: the base case is missing, and in fact \(P(n)\) is false for every \(n\) B \(P(n)\) holds for all \(n\ge1\) C \(P(n)\) holds for all \(n\ge0\) D \(P(n)\) is false only for \(n=0\) Show answer A. Nothing: the base case is missing, and in fact \(P(n)\) is false for every \(n\)← Back to the question
Explanation The inductive step is correct, but without a base case the chain never starts. No \(P(n)\) is true, so the step only links falsehoods.
Mathematical induction proves that a property \(P(n)\) holds for every integer \(n\ge n_0\): one checks the base case \(P(n_0)\) and proves that, for each \(k\ge n_0\), \(P(k)\) implies \(P(k+1)\).
\[\big[P(n_0)\wedge\forall k\ge n_0\,(P(k)\Rightarrow P(k+1))\big]\Rightarrow\forall n\ge n_0\,P(n)\]
More practice problems: mathematical induction