Frage zu Vollständigen Induktion

[noRkia]

hallo ich soll das hier per induktion berarbeiten.aber irgendwie weis ich nich wie man das allgemein zeigen soll,das wir das nie gemacht haben bemerke ich nur mal am rand, aber ich machs mal soweit ichs verstanden hab -.-

"für welche n € N gilt die ungleichung"

2^n > n²

für 1,2,3,4 gilts nicht,das weis ich auch.

induktionsanfang (nachdem man es für 1,2,3,4 ausgerechnet hat)

für n = 5 klappts, is nämlich 32 > 25

induktions vorraussetzung : es klappt nur für n > 4

induktionsschluss: ich setze für n ,(n+1) ein.

2^(n+1) > (n+1)²

<=> 2x2^n > n²+2n+1

so und nun?

das kann unmöglich reichen :D


die schwere aufgabe poste ich (erstmal^o ^) nicht.

[MagicMagor]

Grob gesagt läßt sich ein Beweis per vollständige Induktion in 2 Teile aufspalten:

1. Den sogenannten Induktionsanfang (abgekürzt IA)
2. Den sogenannten Induktionsschrit oder auch Induktionsschluss (IS)

Beim IA zeigt man, daß die zu beweisende aussage (hier 2^n > n^2) für ein bestimmtes n gilt, in der Regel nimmt man n = 0 oder n = 1, aber prinzipiell sind alle möglichen n denkbar.
Beim IS beweist man nun folgendes:
Wenn die Aussage für n gilt, dann gilt sie auch für n+1
Das ist eine bedingte Aussage, über die Größe von n wird hier gar nicht mehr geredet.
Zusammen ergibt sich dann:
1. Die Aussage gilt für (zB) 1 (aus dem IA)
2. Da sie für 1 gilt, sie auch für 2 (Nach dem IS)
3. Da sie für 2 gilt, gilt sie auch für 3 (nach dem IS)
....
Und somit für alle n >= 1.

Das nur mal prinzipiell vorneweg. Nun zu deiner Aufgabe:

Durch rumprobieren hast du schon herausgefunden, daß die Ungleichung erst bei n >=5 gilt, somit macht es Sinn als IA n = 5 zu wählen. Einfach einsetzen und ausrechnen. (Erfahrungsgemäß ist der IA immer sehr einfach)
Beim IS gibt es im Prinzip zwei Ansätze:
1. Du gehst von der Ungleichung für n aus und leitest daraus die Ungleichung für n+1 ab.
2. Du gehst von der Ungleichung für n+1 aus und leitest daraus (per äquivalenzumformungen) die Ungleichung für n ab.
Ich persönlich finde die 1. Variante intuitiver, aber manchmal ist die zweite einfacher. In der Praxis kann man auch beide gleichzeitig anwenden (man leitet also von oben und unten ab und guckt das man sich in der Mitte trifft)

Für deine Aufgabe gehe ich erstmal vom 2. Ansatz aus.
2^(n+1) > (n+1)^2
Ich will zeigen, daß dies äuqivalent zu der Behauptung 2^n > n^2 ist, von der ich per Induktionsvorraussetzung weiß, das sie gilt.
Aufgelöst ergibt obiges:
2^n * 2 > n^2 +2n + 1
umgeformt:
2^n + 2^n > n^2 + 2n + 1
Das 2^n > n^2 ist wissen wir aus der Induktionsvorraussetzung (Die Ungleichung gilt ja für n), was fehlt ist, daß 2^n >= 2n + 1 ist, dann würde die jeweilige Summe natürlich auch größer bleiben. Tatsächlich ist 2^n >= 2n+1, das folgt aus der Bernoulli-Ungleichung (http://de.wikipedia.org/wiki/Bernoullische_Ungleichung) wenn wir x = 1 einsetzen.
Edit: Ok mein Fehler, aus Bernoulli folgt nur 2^n >= n + 1, das für genügend große n auch 2^n >= 2n + 1 gilt sollte einleuchten (da 2^n exponentiell wächst und 2n nur linear) muss aber streng genommen noch bewiesen werden. Läßt sich sicher auch per VI beweisen, spare ich mir hier auf die Schnelle aber mal. Aber sicher eine gute Übung zur VI =)
Damit ist bewiesen, daß obige Ungleichung unter der Vorraussetzung das 2^n > n^2 gilt, richtig ist.

Man kann auch andersherum beweisen:
2^n > n^2 (Induktionsvorraussetzung)
Nach Bernoulli ist 2^n >= 2n + 1 > 0 (x = 1) somit kann ich auf der einen Seite 2^n und auf der anderen 2n+1 addieren ohne die Relation zu verändern:
2^n + 2^n > n^2 + 2n + 1
Das ist äquivalent zu:
2^(n+1) > (n+1)^2
was exakt die zu beweisende Aussage mit n+1 für n ist. Damit und mit dem IA für n = 5 gilt per vollständige Induktion 2^n > n^2 für alle n >=5, n e N.

Ohne Bernoulli ist der Beweis um einiges.. komplizierter, aber möglich.