Behauptung: Für alle \(n\in\mathbb N\) gilt \(n<2^n\).
Beweis per Induktion über \(n\).
Induktionsanfang: Für \(n=1\) ist \(1<2=2^1\).
Induktionsvoraussetzung: Es gebe ein \(n\) für das die Behauptung gilt.
Induktionsschritt: Zu zeigen ist, dass die Behauptung für \(n+1\) gilt.
Nach Induktionsvoraussetzung gilt
\(n+1<2^n+1=2^n+1^n<2^n+2^n=2\cdot2^n=2^{n+1}\).
Daraus folgt die Behauptung.