Proof by strong induction
1. Theorem
Sei \(A(n)\) für beliebiges \(n \in \mathbb{N}\) eine Aussage Dann lässt sich durch folgende zwei Schritte die Gültigkeit der Aussage \(A(n)\) für \(n \in \mathbb{N}\) mit \(n_0 \leq n\) zeigen
1.1. Induktionsanfang:
\(A(n_0)\) ist richtig (\(n_0\) meist \(0\))
1.2. Induktionsschritt
Für \(n \geq n_0\) gilt zu zeigen:
\begin{align*} \forall n \in \mathbb{N} (\forall n' \in \mathbb{N} (n' \leq n \Rightarrow A(n')) \Rightarrow (A(n) \Rightarrow A(n+1))) \end{align*}