(n + 1)!
Zunächst die Fakultät in 2 Faktoren schreiben
= n!·(n + 1)
Jetzt n! durch 2^n abschätzen. Induktionsvoraussetzung
≥ 2^n·(n + 1)
Jetzt n + 1 durch 2 abschätzen
≥ 2^n·2
Jetzt 2^n * 2^1 als 2^(n + 1) schreiben
= 2^(n + 1)
Damit ist der Induktionsschritt fertig.