Induction

Zu zeigen:

∀n (n ≥ 5 \Rightarrow 2^n > n^2)

(Ich lasse n∈N immer weg, sorry)

Beweis über vollständige Induktion.

(Im Allgemeinen sind solche Beweise nicht "mechanisch" findbar und man muss abschätzen)

Induktionsanfang:

n = 5 \Rightarrow 2^n > n^2
n = 5 \Rightarrow 2^5 > 5^2
n = 5 \Rightarrow 32 > 25

Das gilt.

(Das liest man: Angenommen n = 5. Dann muss folgen, dass 2^5 > 5^2. Da 32 > 25 ist, ist gezeigt, dass "wenn n = 5, dann 2^5 > 5^2" gilt)

(Alternativ: Wenn n = 5, dann 2^5 > 5^2. Da 32 > 25 ist gezeigt, dass "wenn n = 5, dann 2^5 > 5^2" gilt)

("gilt" ist ein technischer Ausdruck und heißt, dass eine Aussage immer wahr ist)

Induktionsschritt:

n ≥ 5 ∧ 2^n > n^2 \Rightarrow 2^{n + 1} > (n + 1)^2

Das liest man: Angenommen n ≥ 5 ∧ 2^n > n^2. Dann muss folgen, dass 2^{n + 1} > (n + 1)^2

Da die Wahrheit der Induktionsbehauptung 2^n > n^2 angenommen (vorausgesetzt) wird, kann man sie im Folgenden ungestraft verwenden. Das tun wir jetzt daher.

2^n > n^2
2 ⋅ 2^n > 2 ⋅ n^2

(das ist äquivalent; ich spar mir das dauernde Schreiben von Äquivalenzpfeilen meist, aber eigentlich soll das heißen - ich machs einmal gscheit: 2^n > n^2 \Leftrightarrow 2 ⋅ 2^n > 2 ⋅ n^2)

Zu zeigen ist unter der Annahme n ≥ 5 ∧ 2^n > n^2, dass 2^{n + 1} > (n + 1)^2 folgt. D.h. zu zeigen ist:

n ≥ 5 ∧ 2^n > n^2 \Rightarrow 2^{n + 1} > (n + 1)^2.

Das ist äquivalent zum Zeigen, dass

n ≥ 5 ∧ 2 ⋅ 2^n > 2 ⋅ n^2 \Rightarrow 2^{n + 1} > (n + 1)^2

d.h. äquivalent zum Zeigen, dass (wurde erhalten durch ausmultiplizieren rechts):

n ≥ 5 ∧ 2 ⋅ 2^n > 2 ⋅ n^2 \Rightarrow 2 ⋅ 2^n > n^2 + 2⋅n + 1

Jetzt verwendet man, dass die natürlichen Zahlen und (>) eine Totalordnung bilden, d.h. man muss sie wie auf einer Perlenschnur ohne Schleifen aufreihen können.

Ich versuche, sie aufzureihen.

Laut Annahme ist (n ≥ 5 und) 2 ⋅ 2^n > 2 ⋅ n^2.

Zu zeigen ist 2 ⋅ 2^n > n^2 + 2⋅n + 1.

Aber um sie richtigherum aufzureihen (nicht die n, sondern die Zahlen wie 2 ⋅ 2^n, 2 ⋅ n², n^2 + 2⋅n + 1):

Mehr zeigen

Ist 2 ⋅ n^2 > n^2 + 2⋅n + 1 ?

Das geht zB über Herausheb-Trickserei (bitte die "<=>" dazudenken - wenn man die immer schreibt, kann man vor lauter Doppelpfeilen nix mehr lesen):

2 ⋅ n^2 > n^2 + 2⋅n + 1
n^2 > 2⋅n + 1
n⋅n > 2⋅n + 1
n⋅(n - 2) > 1

Das ist mindestens der Fall, wenn "n > 1 und n - 2 > 1", d.h. "n > 1 und n > 3", d.h. "n > 3". Gut, dass unsere Zusatzbedingung n ≥ 5 fordert, sonst hätten wir an der Stelle vielleicht ein Problem.

Jetzt haben wir gezeigt, dass für n > 3 folgt 2 ⋅ n^2 > n^2 + 2⋅n + 1.

D.h. formal gilt:

n > 3 \Rightarrow 2 ⋅ n^2 > n^2 + 2⋅n + 1

Aber es gilt auch:

n ≥ 5 \Rightarrow n > 3
n ≥ 5 \Rightarrow n > 3 \Rightarrow 2 ⋅ n^2 > n^2 + 2⋅n + 1
n ≥ 5 \Rightarrow 2 ⋅ n^2 > n^2 + 2⋅n + 1

Andererseits

n ≥ 5 \Rightarrow 2 ⋅ 2^n > 2 ⋅ n^2 (Annahme)

Aber zu zeigen ist: 2 ⋅ 2^n > n^2 + 2⋅n + 1 (KEINE Annahme, DO NOT USE)

Daher

n ≥ 5 \Rightarrow 2 ⋅ 2^n > 2 ⋅ n^2 > n^2 + 2⋅n + 1

"A > B > C" ist eine suggestive Kurzschreibweise für "A > B ∧ B > C", die einen daran erinnern soll, dass ">" transitiv ist und man das "> B" in der Mitte auch einfach weglassen darf. Jedenfalls sind da die Zahlen "auf der Perlenkette" in absteigender Reihenfolge aufgelistet, möglicherweise unter Weglassung uninteressanter Zahlen.

Also tu ich das "> B" weglassen:

n ≥ 5 \Rightarrow 2 ⋅ 2^n > n^2 + 2⋅n + 1

Äquivalent zu

n ≥ 5 \Rightarrow 2^{n + 1} > (n + 1)^2

Was zu zeigen war.

Damit ist der Beweis erbracht, jedenfalls solange n ≥ 5 und 2^n > n^2.

Insgesamt lautet die bewiesene Behauptung formal:

∀n ((n ≥ 5 ∧ 2^n > n^2) \Rightarrow 2^{n + 1} > (n + 1)^2)

Im Allgemeinen wichtig ist, dass man die rechte Seite von "=>" nicht verwenden (als Wahrheit anerkennen) darf, bevor der Beweis dafür fertig ist, dass sie sowieso automatisch aus der zugehörigen linken Seite folgt (was jetzt geschehen ist).

Wegen den Axiomen der natürlichen Zahlen (u.a. Induktionsaxiom) gilt daher auch:

∀n (n ≥ 5 \Rightarrow 2^n > n^2)

Author: Danny (remove the ".nospam" to send)

Last modification on: Sat, 04 May 2024 .