Behauptung: Für alle
n∈N gilt
n<2n.
Beweis per Induktion über
n.
Induktionsanfang: Für
n=1 ist
1<2=21.
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<2n+1=2n+1n<2n+2n=2⋅2n=2n+1.
Daraus folgt die Behauptung.