Beweise 2^n ≥ n^2 für n≥ 4 | Vollständige Induktion

Question

Aufgabe: Beweise mittels vollständiger Induktion
2^n ≥ n^2 für n ≥ 4

Problem/Ansatz:

Ich komme nach Induktionsanfang und Voraussetzung zu:
2ⁿ⁺¹ ≥ (n + 1)^2
2*n^2 ≥ n^2 +2n +1
=> n^2+2n -2n +n^2 ≥ n^2 +2n +1
Diese Ungleichung muss ja für
-2n+n^2 ≥ 1 richtig sein. Allerdings kann man ja leider auch in diese die 3 einsetzen, was meine Lösung falsch macht.

Was habe ich falsch?

Answer 1

Hallo :-)

Wie kommst du von der ersten Zeile auf die zweite Zeile \(2\cdot n^2 ≥ n^2 +2\cdot n +1\)?

Comments

2ⁿ⁺¹ ≥ (n + 1)²
2ⁿ * 2¹ ≥ n² +2n +1
Unter Induktionsvorausetzung von 2ⁿ ≥ n² setze 2ⁿ gleich n²

^{\(2\cdot n^2 ≥ n^2 +2\cdot n +1\)}

:)

---

Er hat benutzt das 2^n ≥ n^2 ist und damit die linke Seite nach unten abgeschätzt.

---

Ah verstehe. Das sollte man aber besser nicht so machen, weil es im ungünstigsten Fall passieren kann, dass durch eine zu grobe Abschätzung nach unten einer Seite, die neu entstandene Ungleichung (mit den vorausgesetzten Nebenbedingungen) falsch ist. Außerdem ist der Sinn im Induktionsschritt, die Umformungen so zu gestalten, dass am Ende die Induktionsbehauptung rauskommt. Denn so hat man ja gezeigt, dass die Behauptung für alle natürlichen Zahlen (ab einen Startwert) wahr ist. Startet man hingegen gleich mit der Behauptung (was hier getan wird) und sie im ungünstigsten Fall auch noch falsch ist, so kann man daraus alles Mögliche schlussfolgern (aus falschen Aussagen lassen sich wahre Aussagen schlussfolgern).

Fange also auf eine der beiden Seiten an und schätze so passend ab, um zur Behauptung zu gelangen.

Lange Rede kurzer Sinn. Eine Umsetzung würde so aussehen:

$$ \begin{aligned}&2^{n+1}\\[5pt]&=2\cdot 2^n\\[5pt]&\stackrel{(IV)}{\geq }2\cdot n^2\\[5pt]&=n^2+n^2\\[5pt]&=n^2+n\cdot n\\[5pt]&=n^2+n\cdot \left(\frac{1}{2}\cdot n+\frac{1}{2}\cdot n\right)\\[5pt]&\stackrel{n\geq 4}{\geq}n^2+n\cdot \left(\frac{1}{2}\cdot 4+\frac{1}{2}\cdot n\right)\\[5pt]&=n^2+2\cdot n+\frac{1}{2}\cdot n^2\\[5pt]&\stackrel{n\geq 4}{\geq }n^2+2\cdot n+\frac{1}{2}\cdot 4^2\\[5pt]&=n^2+2\cdot n+8\\[5pt]&\geq n^2+2\cdot n+1\\[5pt]&=(n+1)^2 \end{aligned}$$

Answer 2

n^2 - 2·n ≥ 1

Das dieses sogar für n = 3 gilt, macht deine Lösung nicht falsch. Deine Lösung stimmt, weil es für alle n ≥ 4 wahr ist.

Comments

In der HA muss ich leider spezifisch auf n=3 eingehen. Es ist ja klar, dass

2^3 ≥ 3² falsch ist. Mit meiner Lösung kann ich dies aber nicht schön zeigen.

---

Die Vollständige Induktion ist doch hier auch nur dazu da zu zeigen dass es für n >= 4 gilt.

und du zeigst ja das wenn es für n gilt es auch für n + 1 gilt.

Wenn du also für n = 3 einsetzt, dann bist du dabei zu zeigen das es für n + 1 = 4 gilt und das gilt ja.

also musstest du für n = 2 einsetzen

2^2 - 2*2 = 0 >= 1 ist verkehrt

also daraus zu schließen das wenn es für 2 gilt dann darauf zu schließen das es auch für n + 1 = 3 gilt wäre verkehrt. Und es gilt ja für n = 2 und für n = 3 eben nicht.

---

Alles klar,

Ich denke ich hab's verstanden!

Vielen Dank!

Answer 3

Hallo,

wenn du hier n=3 einsetzt, ist die Ungleichung auch erfüllt, da n+1=3+1=4 ist und 2^4=4^2.

2^{n+1} ≥ (n + 1)^2

2^{3+1} ≥ (3 + 1)^2

Da du die Induktionsvoraussetzung verwendest, die ja nicht für n=3 gilt, scheinst du aus etwas Falschem etwas Richtiges zu folgern. Du darfst die Voraussetzung ja nur verwenden, wenn sie für einen Wert richtig ist.