0 Daumen
1,7k Aufrufe

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

Problem/Ansatz:

Ich komme nach Induktionsanfang und Voraussetzung zu:
2n+1 ≥ (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?

Avatar von

3 Antworten

0 Daumen
 
Beste Antwort

Hallo :-)

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

Avatar von 15 k

2n+1 ≥ (n + 1)2
2n * 21 ≥ n2 +2n +1
Unter Induktionsvorausetzung von 2n ≥ n2 setze 2n gleich n2

\(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}$$

0 Daumen

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.

Avatar von 487 k 🚀

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!

0 Daumen

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.

Avatar von 47 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community