Zwischenbeweis der vollst. induktion von n^2<=2^n für n element IN ohne 3.

Question

auf dieser Seite und auf vielen Anderen kann ich die richtige Lösung zu diesem Beweis finden,aber ich verstehe einen Schritt nicht,den ich mir leider nicht selbst erklären kann,da es für mich andersrum sein muss.

Folgendes: Ich muss beweisen,dass (n+1)^2 <=2^{n+1}

Beim Induktionsschritt schreibe ich:

n^2 <= 2^n (Addiere 2n +1 links und rechts).

n^2 + 2n + 1 <= 2^n + 2n + 1

(n+1)^2 <= 2^n + 2n + 1

Jetzt muss ich meiner Meinung nach beweisen,dass 2^n+2n + 1 >= 2^{n+1} ist und dann komm ich auf 2n + 1 >=2^n. Es sollte aber genau andersrum sein, also 2n + 1<= 2^n. Ich verstehe aber nicht wieso. Wenn  (n+1)^2 <= 2^{n+1} und 2^n+2n+1 >= 2^{n+1}, dann ist doch (n+1)^2 kleiner als 2^{n+1}. 

Answer 1

(n+1)² <= 2ⁿ + 2n + 1

Jetzt muss ich meiner Meinung nach beweisen,dass 2ⁿ+2n + 1 >= 2ⁿ⁺¹ ist 

Du musst zeigen, dass  2ⁿ+2n + 1 ≤  2ⁿ⁺¹ ist  (#)  , denn dann hast du  

(n+1)² ≤  2ⁿ + 2n + 1 ≤  2ⁿ⁺¹

 2ⁿ+2n + 1 ≤  2ⁿ⁺¹ 

⇔   2ⁿ+ 2n + 1 ≤  2 * 2ⁿ  =  2ⁿ + 2ⁿ

⇔     2n + 1 ≤  2ⁿ 

Beide Terme sind streng monoton wachsend  und  2 * 3 + 1 ≤  2³ 

+ vgl. Kommentare 

#  ist also für n≥3  wahr

Gruß Wolfgang

Comments

2n + 1 ≤  2ⁿ 

Beide Terme sind streng monoton wachsend  und  2 * 3 + 1 ≤  2³ 

Das reicht nicht aus. Entscheidend ist doch, dass die rechte Seite stärker streng monoton wächst.

---

"Das reicht nicht aus. Entscheidend ist doch, dass die rechte Seite stärker streng monoton wächst."

Zum einen: Was heißt das überhaupt? Und zum anderen: Würde das denn ausreichen?

---

@jc2144

Da hast du natürlich recht. Danke für den Hinweis.

Spontan fällt mir dazu ein, dass der Funktionsterm 2^x eine linksgekrümmte Funktion darstellt, seine Steigung also ständig größer wird, während der Geradenterm 2x+1 eine konstante Steigung hat. 

---

Ja das wäre eine Begründung. Vermutlich ist Differentiation jedoch noch nicht in der Vorlesung behandelt, deshalb könnte man auch die Hilfsungleichung  mit einer weiterer Induktion zeigen.

---

Erstmal danke ich euch für die hilfreichen Antworten! Mittlerweile denke ich,dass ich  meinen Fehler endlich erkenne. Es ist ja so,dass mein ganzer Beweis darauf aufgebaut ist,dass (n+1)^2<= 2^n +2n +1 ist und nachdem ich dies beweise,ist (n+1)^2 wie bewiesen  kleiner/gleich als 2^{n+1}. Kann man sagen,dass (n+1)^2<= 2^n +2n +1   die strengere Bedingung ist und ich deswegen (n+1)^2<=2^{n+1}<=2^n+2n+1 nicht schreiben kann?

Answer 2

Hallo mbsa07! :-)

Jetzt muss ich meiner Meinung nach beweisen,dass 2ⁿ+2n + 1 >= 2ⁿ⁺¹ ist

Nimm doch die entgegengesetzte Richtung, beweise,
dass 2ⁿ + 2n + 1 <= 2^{n +} 2ⁿ = 2· 2ⁿ = 2ⁿ⁺¹ ist indem Du zeigst, dass 2n + 1 <=  2ⁿ ab einem bestimmten n gilt.

Beste Grüße

Comments

Meine Frage ist ja genau,warum es in die entgegengesetzte Richtung sein muss.

---

Die Richtung ist in der Aufgabenstellung vorgegeben: n² <= 2ⁿ 

I-Schritt:
(n+1)² <= 2ⁿ + 2n + 1  <=  2^{n +} 2ⁿ = 2· 2ⁿ = 2ⁿ⁺¹

Also insgesamt (n+1)² <= 2ⁿ⁺¹
keine Ahnung warum Du die Richtung wechseln möchtest.

Du kannst es gern auch kompliziert machen und annehmen, dass 2ⁿ+2n + 1 > 2ⁿ⁺¹  gilt. Das führt zu einem Widerspruch, was zur Folge hat, dass 2ⁿ + 2n + 1 <= 2ⁿ⁺¹ gelten muss.