Ungleichungen wie 2^n > n mit Hilfe der vollständigen Induktion beweisen

Question

Beweisen Sie die Ungleichungen mit Hilfe der vollständigen Induktion:
2^n > n für n∈ℕ

2^n > n^2 für n≥5

2^n > n^3 für n≥10

Answer 1

"vollständige Induktion"sbeweise gehen meistens so von der Hand:

Basis: n = 1, 2^1 > 1 ✓ (wahre Aussage)

(Induktionsvoraussetzung: 2^n > n)

Induktionsschritt: 2^{n + 1} = 2^n * 2 > n * 2 > n + 1 ✓ (wahre Aussage) q.e.d.

Das Prinzip ist, dass die Aussage H(n) für eine bestimmte "Basis" ("Induktionsanfang") bewiesen wird. Dann wird unter H(n) (Induktionsvoraussetzung) bewiesen, dass H(n + 1) gilt. Das heißt, dass dann die gesamte Aussage H(n) für alle n größer gleich dem Startwert (hier n = 1) gilt, da sie für 1, 1+1=2, 2+1=3, 3+1=4, ... (n)+1 = (n+1) gilt.

Die anderen beiden Aussagen kannst du vielleicht jetzt selber rechnen.

MfG

Mister

Comments

n * 2 ist nicht zwangsläufig größer als n+ 1
die beiden Ausnahmen: n = 1 (2 = 2) oder n = 0 (0 < 1)

---

mag sein, dass ich total auf dem Schlauch stehe, aber woher kommen im Induktionsschritt

die 2*n?

---

Die kommen aus der Induktionsvoraussetzung (2^n > n und 2 = 2).