vollständige Induktion zu einer Ungleichung zu zeigen: 2(n+1)+1 ≤ (n+1)^2 ≤ 2^{n+1}

Question

Ich habe mit folgender Aufgabe Probleme:

Beweisen Sie mit vollständiger Induktion, dass 2n+1 ≤ n^² ≤ 2ⁿ für alle n ≥ 4 gilt.

Ich weiß was zu zeigen ist, nämlich: 2(n+1)+1 ≤ (n+1)² ≤ 2ⁿ⁺¹

wie gehe ich nun weiter an die aufgabe dran um Schritt für Schritt die Behauptung zu beweisen?

Answer 1

mach es besser in 2 Teilen:  Erst Mal   2n+1 ≤ n^²

für  n= 4 stimmt eszu zeigen:  wenn es für n stimmt, dann auch für n+1Sei als0   2n+1 ≤ n^²   dann folgt               2n+1  +2  ≤ n^²   + 2

<=>       2(n+1) + 1 ≤ n^²   + 2
 
Da aber 2n>1 für alle n≥4 ist, gilt auch 


2(n+1) + 1 ≤ n^²   +2n  +  1   =  (n+1)²  .   q.e.d.

Für den 2. Teil bekommst du es bestimmt auch hin.

Answer 2

Ich schlage vor, die Doppelungleichung 2n+1 ≤ n^² ≤ 2ⁿ in zwei Ungleichungen zu zerlegen, die dann getrennt zu beweisen sind:

1.) 2n+1 ≤ n^²

2.) n^² ≤ 2ⁿ

Um 1.) zu beweisen, stellen wir einen Hilfssatz bereit: n²+2≤n²+2n+1 (das ist leicht zu beweisen)

Dann addieren wir in 2n+1 ≤ n^² auf beiden Seiten 2

2n+3 ≤ n^² + 2 Jetzt setzen wir den Hilfssatz ein

2n+3 ≤ n²+2n+1

Nun formen wir um

2(n+1)+1 ≤ (n+1)². Was zu zeigen war.

Answer 3

2·n + 1 ≤ n^2 ≤ 2^n für alle n ≥ 4

Induktionsanfang: n = 4

2·4 + 1 ≤ 4^2 ≤ 2^4

9 ≤ 16 ≤ 16 --> stimmt

Induktionsschritt: n --> n + 1

2·(n + 1) + 1 ≤ (n + 1)^2 ≤ 2^{n + 1}

2·n + 1 + 2 ≤ n^2 + 2·n + 1 ≤ 2^n + 2^n

Das Grüne ist die Induktionsannahme.

Das Rote ist doch leicht zu beweisen oder?

Comments

also irgendwie hab ich das nicht ganz verstanden:

wenn ich bei der Doppelungleichung zunächst nur folgendes betrachte:

2 n+1 ≤ n²

zu zeigen ist --> 2(n+1)+1 ≤ (n+1)²

als nächstes setze ich die Annahme für 2(n+1) ein also die n²

dann bleibt doch folgendes stehen: n² +1 und da hierbei die 1 > 0 ist erfolgt hiermit der beweis für den ersten Teil, dass n²≤ n²+1

oder nicht?

---

Nein. Hier setzte ich nichts ein.

a + b < c + d

ist auf jeden Fall wahr wenn a < c und b < d ist.

Also mache ich daraus einmal die Induktionsannahme und einen Rest. Das sollte oben eigentlich hervorgehen, dass ich da nicht irgendwas ersetzt habe. Was ich gemacht habe ist ausmultipliziert.

---

Sorry, hatte vergessen zu erwähnen, dass ich in einem Video gesehen habe, dass quasi immer der rechte Teil der Annahme für die zu zeigende linke Seite eingesetzt wird und daher versucht die Aufgabe nach diesem Schema zu lösen. Wäre mein Gedankengang denn so korrekt oder liege ich da völlig daneben?

---

Naja. Nimm mal die Zeile

2·n + 1 + 2 ≤ n² + 2·n + 1

Nun kannst du natürlich den grünen Term der linken Seite durch den Grünen Term der rechten Seite abschätzen, also einsetzen. Und dann kannst du ihn auf beiden Seiten wegnehmen. Übrig bleibt dann der Rote Term. Daher braucht man hier nur den roten Term zeigen.

So spart man sich noch etwas an Umformungen.