Induktionen bei Ungleichung. Zeigen Sie: Für alle n ∈ N mit n > 4 gilt: 2^{n} > n^{2} .

Question

ich habe eine Problem bei der folgenden Aufgabe.

Aufgabe 1.2 Zeigen Sie: Für alle n ∈ N mit n > 4 gilt: 2^{n} > n^{2} .

und spule mal direkt vor zu dem Induktionsschritt.

Link zur Aufgabe: http://www.ma.tum.de/foswiki/pub/HM/EI1WiSe0910/Blaetter/blatt01-lsg.pdf

Induktionsschritt (n → n+1) 

Zu zeigen ist, dass die Behauptung unter dieser Voraussetzung auch für n+1 gilt, wir müssen also beweisen, dass 2^{n+1} > (n+1)^{2} . Dazu formen wir ein bisschen um: 2^{n+1} = 2 · 2^{n} > 2 · n^{2} .

Im letzten Schritt haben wir die Induktionsvoraussetzung für den Term 2^{n} eingesetzt. Werfen wir mal einen Blick auf die rechte Seite:

(n + 1)^{2} = n^{2} + 2n + 1. Wir haben noch zu zeigen, dass n^{2} ≥ 2n + 1 gilt (hier genügt „≥“, das „>“ haben wir ja beim Einsetzen der Induktionsvoraussetzung bereits sichergestellt). Wenn das bewiesen wäre, könnten wir oben einfach weitermachen: 2^{n+1} = · · · > 2 · n^{2} = n^{2} + n^{2} ≥ n^{2} + (2n + 1) = (n + 1)^{2}

Schaut man bei dem Einsetzen von IV bei 2^{n+1} = 2 · 2^{n} > 2 · n^{2} . Das der rote Ausdruck größer ist als (n+1)^{2} ?

Wieso muss man das n^{2} ≥ 2n + 1 beweisen man hat doch schon mit  2^{n+1} = 2 · 2^{n} > 2 · n^{2} . bewiesen bzw. mit 2^{n+1} = · · · > 2 · n^{2} = n^{2} + n^{2} ≥ n^{2} + (2n + 1) = (n + 1)^{2} gezeigt das 2^{n+1} > (n+1)^{2} ist.

Und wieso schreibt man bei ... 2 * n^{2} + (2n + 1) = (n + 1)^{2} das (2n + 1) in Klammern? Könnte man das auch ohne Klammern aufschreiben ? Ich vermute ja wenn man das so schreibt, schreit es für mich nach Distributivgesetz. Ist es möglich das man das hier anwenden kann oder wurde es benutzt? Man benutzt doch nur die Binomische Formeln für das auswerten und größer gleich vergleichen von (n + 1)^{2}.

Kann mir jemand meinen Denkfehler zeigen oder bestätigen ob ich das ganze richtig verstehe ? Man versucht ja wie bei Vollständigen Induktionen mit Summenzeichen das n+1 zu beweisen. Man macht hier genau das selbe, jedoch verstehe ich einzelne Schritte die ich oben "Erklärt" habe noch nicht ganz. Also kann mir jemand den Fehler erklären bzw. warum man  n^{2} ≥ 2n + 1 beweisen muss etc.

LG

ClassicSalvatore

Answer 1

Wieso muss man das n² ≥ 2n + 1 beweisen man hat doch schon mit  2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n² . bewiesen bzw. mit 2ⁿ⁺¹ = · · · > 2 · n² = n² + n² ≥ n² + (2n + 1) = (n + 1)² gezeigt das 2ⁿ⁺¹ > (n+1)² ist. 

Antwort: "Wenn man 2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n² als bewiesen ansieht, muss nichts mehr bewiesen werden."

Und wieso schreibt man bei ... 2 * n² + (2n + 1) = (n + 1)² das (2n + 1) in Klammern? Könnte man das auch ohne Klammern aufschreiben ?
Antwort: "Ja."

Comments

ich konnte jetzt nicht aus der Antwort entnehmen ob 2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n²   bewiesen wurde.

Also beweist  2ⁿ⁺¹ = · · · > 2 · n² = n² + n² ≥ n² + (2n + 1) = (n + 1)²   den Induktionsschritt 2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n²  ?

Ist n² ≥ 2n + 1 zu beweisen jetzt unnötig ? Wie kommt man überhaupt darauf ?

Falls irgendetwas nicht richtig ist wegen der Terminologie, entschuldige ich mich im Voraus habe das ganze noch nicht so drauf.

Gruß Salva

---

"ich konnte jetzt nicht aus der Antwort entnehmen ob 2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n²   bewiesen wurde."

Das habe nicht ich behauptet, sondern du.

Mal grundsätzlich zum Induktionsbeweis:

A(n) sei eine Aussage über n, die bewiesen werden soll. Dann ist die Induktionsvoraussetzung: Es gibt ein n, für das A(n) gilt. Der Induktionsschluss lautet dann A(n)⇒A(n+1), Also: Unter der Voraussetzung, dass A(n) gilt, gilt auch A(n+1). Die entscheidende Überlegung (die jetzt einsetzt) wird meistens weder aufgeschrieben noch erwähnt: Da A(1) gilt (1=Induktionsanfang), gilt auch A(2). Da jetzt A(2) gilt, gilt auch A(3). Da jetzt A(3) gilt, gilt auch A(4). Und so weiter und so weiter.

Die besondere Kunst des Induktionsbeweises besteht aber nicht in diesem Gedankengang, sondern in der Folgerung  A(n)⇒A(n+1). Diese Folgerung erfordert  viel Termumformung und Gleichungslehre (hier Ungleichungslehre). Aus 2ⁿ > n² soll gefolgert werden: 2ⁿ⁺¹ > (n+1)². Dazu addieren wir zu 2ⁿ > n² die Ungleichung 2ⁿ>2n+1. Diese muss separat bewiesen werden, denn bisher ist ja noch gar nichts bewiesen. Außerdem darf man das, was bewiesen werden soll, im Beweis nicht verwenden.

---

ja ich habe behauptet bzw. gefragt ob 2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n² jetzt bewiesen wurde, da war ich mir nicht sicher.

"Also beweist  2ⁿ⁺¹ = · · · > 2 · n² = n² + n² ≥ n² + (2n + 1) = (n + 1)²   den Induktionsschritt 2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n²  ?" 

Am Anfang hat man ja schon gezeigt bzw. bewiesen mit  n= 5 also das A(n) bzw. das kleinst möglichste n wird ja für A(n) eingesetzt in 2ⁿ > n^2.  Was für die Bedingung  n ∈ N mit n > 4 gilt und das ist 5. Man setzt 5 für A(n) =  2ⁿ > n²  die 5 ein und wenn man das im Kopf schnell rechnet hat man 32 > 25. (Induktionsanfang)

Jetzt kommt der InduktionssVoraussetzung:

Welche für n ∈ N mit n ≥ 5 gilt.

IV: A(5...) =  2ⁿ > n²    (Formal bestimmt nicht richtig soll nur das "vorhandene"                                           Verständnis zeigen)

Kommentar folgt..

---

Dann folgt der Induktionsschritt der zeigt A(n) -> (wenn dann) A(n+1). Wenn A(n) gilt , gilt auch A(n+1). Dies gilt ja zu beweisen: 

Und würde folgendermaßen aussehen: 2^{n+1} > (n+1)^{2} . Das hier gilt zu beweisen.

So dann zum Beweis selbst:

2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n²   Hier hat man zuerst gezeigt das 2ⁿ⁺¹ = 2 · 2ⁿ gleich ist. und für 2n  die Induktionsvoraussetzung eingefügt welche besagt: 2ⁿ > n². Nun erhält man > 2 · n² weil man 2ⁿ mit n² ersetzt . (Wie bei dem Summenzeichen welches ja auch ersetzt wird.) 

So weit komme ich alleine wenn ich die Lösungen nicht benutzte. Mit der Lösung habe ich dann Verstanden das  2ⁿ⁺¹ = · · · > 2 · n² = n² + n² ≥ n² + (2n + 1) = (n + 1) den Induktionsbeweis 2ⁿ⁺¹ = 2 · 2ⁿ > 2 · n²  "beweist". 

---

Ich verstehe nicht wie man auf diesen Schritt kommt.

 "Dazu addieren wir zu 2ⁿ > n² die Ungleichung 2ⁿ>2n+1  Diese muss separat bewiesen werden,.."

Danke wenn Sie das hier durchlesen. Ich hoffe das ist verständlich und erklärt wie ich an die Vollständige Induktion herangehe und versuche sie zu Lösen. Bzw. den Grad der "Verständnis".

Gruß 

Salva

---

2ⁿ⁺¹ > (n+1)² . Das hier gilt es zu beweisen. Ja! Wenn du jetzt im Beweis rückwärts gehst, kommst du zu 2 · 2ⁿ > 2 · n² und das müsste heißen 2 · 2ⁿ > 2 · (n+1)² . Ich schreibe diese Zeile so 2ⁿ+2ⁿ>n²+2n+1. Wenn ich also die beiden Ungleichungen 2ⁿ>n² (Voraussetzung) und 2ⁿ>2n+1 (noch zu beweisen) addiere, kommt 2ⁿ+2ⁿ>n²+2n+1 heraus.