n^2 < 2^n per Induktion beweisen - Seite 2

15.11.2009, 16:43

SoerenC

Wir reden aneinander vorbei (du denkst ich lese deine antworten nicht richtig. ich denke, du liest meine nicht richtig). Egal. Danke, für Deine Mühe. Alles Gute!

Der Beweis wäre formal genauso verlaufen, wenn wir einfach definiert hätten, dass n>0 sein muss, wenn wir es für n=1 getestet hätten. Dass es bei n=3 nicht stimmt, wissen wir ja nur, weil wir zufällig Glück gehabt haben.

15.11.2009, 16:46

kiste

Auf diesen Beitrag antworten »

Naja wenn du meinst. Ich habe genau deine Frage beantwortet warum das eben nicht sein kann was du behauptest.

Schönen Sonntag noch

Edit: Nein der Beweis wäre nicht durchgegangen wenn wir mit n=1 angefangen haben, weil wir, ich sage das jetzt zum letzten Mal, $\begin{eqnarray*} 2n+1\leq n^2 \end{eqnarray*}$ in unserem Beweis benutzt haben. Und diese Ungleichung gilt nunmal für n=1 noch nicht sondern erst ab n>= 3

15.11.2009, 16:58

SoerenC

Auf diesen Beitrag antworten »

Ich habe nicht behauptet, dass der Beweis für n=1 durchgehen kann. Dass weiß ich aber nur, weil ich zufällig weiß, dass der Beweis für n=3 nicht geht. Aber nehmen wir an, ich wüsste nicht, dass die Ungleichung für n=3 nicht gilt. Und es wäre definiert, dass er für n>0 gilt. Dann hätte der Beweis rein formal 100% genau so ausgesehen.

Weil ich jetzt aber "zufällig" weiß, dass die Ungleichung für n=3 nicht gilt. Kann ich dann einfach so behaupten, dass er für alle n>3 gilt, da er doch formal für n>0 genau so verlaufen würde? Woher also weiß ich, dass n=4 die unterste Schranke ist. Denn die Ungleichung funktioniet ja auch für n=1, n=2. Nur bei n=3 gibt es eine Lücke.

15.11.2009, 17:16

kiste

Auf diesen Beitrag antworten »

Schön das du das rein formal fett schreibst. Vergleiche es mit meinem Fett-geschriebenen und du erkennst dass der Beweis in diesem Fall eben nicht so aussehen kann.

Unser Beweis hat also benutzt dass wir n>= 3 haben...

Das n=4 die untere Schranke ist muss man eben durch Erfahrung oder ausprobieren rausbekommen. Der Beweis liefert dann die Gewissheit

19.11.2009, 23:22

SoerenC

Auf diesen Beitrag antworten »

So, jetzt dürfte es stimmen:

zu zeigen $\begin{eqnarray*} n^2 \ge 2^n \ \forall n > 3 \end{eqnarray*}$

Probe für n=5: $\begin{eqnarray*} 5^2 = 25 \ge 2^5 = 32 \end{eqnarray*}$ OK

IS: $\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$
$\begin{eqnarray*} (n+1)^2 \le 2^n \end{eqnarray*}$
$\begin{eqnarray*} (n+1)^2 \le 2 * 2^n \end{eqnarray*}$
$\begin{eqnarray*} (n^2 + 2n + 1) \le 2^n + 2^n \end{eqnarray*}$

Somit $\begin{eqnarray*} (n^2 + 2n + 1) \le n^2 + n^2 \le 2^n + 2^n \ \forall n > 3 \end{eqnarray*}$
Daher ist nachzuweisen, dass $\begin{eqnarray*} (2n+1) \le n^2 \end{eqnarray*}$
Probe für n=3 ergibt $\begin{eqnarray*} 7 \le 9 \end{eqnarray*}$ , was OK ist.
Somit folgt Beweis separat für A(n) nach A(n+1)
$\begin{eqnarray*} 2(n+1)+1 \le (n+1)^2 \end{eqnarray*}$
$\begin{eqnarray*} 2n+3 \le n^2 + 2n +1 \end{eqnarray*}$
$\begin{eqnarray*} 2 \le n^2 \end{eqnarray*}$ , was für alle n > 3 offensichtlich ist.
Somit folgt $\begin{eqnarray*} n^2 \le 2^n \ \forall n > 3 \end{eqnarray*}$

20.11.2009, 05:33

Egal

Auf diesen Beitrag antworten »

Das sieht nicht schlecht aus. Allerdings würd ich die Verankerung ganz am Anfang für 4 machen. Das es für 4 gilt hast du nämlich noch nicht gezeigt.

20.11.2009, 06:38

Mystic

Auf diesen Beitrag antworten »

Ja, wenn dieser "Beweis" der allererste Versuch hier in diesem Thread gewesen wäre, könnte man sagen, man muss zwar da und dort noch einiges ändern, aber man kann die Sache "reparieren", nach den seitenlangen Bemühungen von Kiste und meinerseits (insbesondere meinem "Fastbeweis", wo es ja nur mehr eine winzige Lücke gab), vor allem aber auch, nachdem du die Lösung in der Übungsstunde inzwischen schon gehört hast, ist das jetzt einfach nur niederschmetternd... unglücklich

Hier zum Vergleich mein "Fastbeweis" von $\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$ in diesem Thread, nämlich

$\begin{eqnarray*} (n+1)^2 = n^2+\underbrace{2n+1}_{\le n^2} \le n^2+n^2=2\underbrace{n^2}_{\le 2^n}\le 2 \cdot 2^n =2^{n+1} \end{eqnarray*}$

und hier nochmals komplett, d.h., mit "ausgefüllter Lücke" (man sieht insbesondere, dass dieser Schluss nur für n>2 so funktioniert, da ich dies zwischendurch zusammen mit A(n) verwende!)

$\begin{eqnarray*} (n+1)^2 = n^2+\underbrace{2}_{<n}n+1 \le n^2+n^2\le2\underbrace{n^2}_{\le 2^n}\le 2 \cdot 2^n =2^{n+1} \end{eqnarray*}$

d.h., diese eine Zeile in Verbindung mit dem Nachweis der Richtigkeit der Behauptung für n=4 ist der ganze(!) Beweis, was also nochmals sehr deutlich zeigt, wie kurz er eigentlich ist und wie wenig nur noch gefehlt hat...

20.11.2009, 09:52

klarsoweit

Auf diesen Beitrag antworten »

So, jetzt mische ich mich auch noch ein.

Zitat:

Original von BaldrianForte
zu zeigen $\begin{eqnarray*} n^2 \ge 2^n \ \forall n > 3 \end{eqnarray*}$

Es fängt schon damit an, daß die Behauptung falsch ist. Richtig ist:
$\begin{eqnarray*} n^2 \leq 2^n \ \forall n > 3 \end{eqnarray*}$

Zitat:

Original von BaldrianForte
Probe für n=5: $\begin{eqnarray*} 5^2 = 25 \ge 2^5 = 32 \end{eqnarray*}$ OK

Zu einem machst du da nicht den Induktionsanfang für n=4, zum anderen sollte dir spätestens da auffallen, daß 25 nicht größer-gleich 32 ist.

Zitat:

Original von BaldrianForte
IS: $\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$
$\begin{eqnarray*} (n+1)^2 \le 2^n \end{eqnarray*}$
$\begin{eqnarray*} (n+1)^2 \le 2 * 2^n \end{eqnarray*}$
...
Somit folgt $\begin{eqnarray*} n^2 \le 2^n \ \forall n > 3 \end{eqnarray*}$

Hier offenbart sich einmal mehr, daß du das Prinzip der vollständigen Induktion nicht verstanden hast. Im einzelnen:
Du schreibst: $\begin{eqnarray*} (n+1)^2 \le 2^n \end{eqnarray*}$
Wo nimmst du das her? Das ist weder A(n) noch A(n+1) .

In der weiteren Abfolge nimmst du A(n+1) und folgerst daraus A(n). Der Beweis geht aber gerade andersherum. Du mußt A(n) nehmen und daraus A(n+1) folgern.

29.11.2009, 19:47

dieAnna

Auf diesen Beitrag antworten »

ähnliches Beispiel
Hallo.

Ich bin mir nicht ganz sicher, obich das Prinzip der vollständigen Induktion richtig verstanden habe, weil ich nicht genau weiß wie ich die IV anwenden kann bzw. wie es dann weiter geht.

Also ich schreib erstmal hin, wie ich denke wie Induktion überhaupt funktioniert (vllt. ist da ja schon i.-wo ein Denkfehler):

Man hat eine Gleichung oder Ungleichung, die man beweisen soll durch vollständige Induktion.

Also schreibt man zunächst mal die Behauptung hin.

Dann:

Induktionsanfang: Hier suche ich einen geeigneten Startwert und setze diese Zahl in beide Seiten der Gleichung /Ungleichung ein und zeige damit, dass die Behauptung für meinen no wahr ist.

Dann schreib ich meine Behauptung einfach noch mal hin und nenne das ganze Induktionsvoraussetzung.

Dann schreib ich hin, was zu zeigen ist, nämlich die linke Seite der Gleichung mit n+1 und die Rechte Seite der Gleichung mit n+1.

Als nächstes Suche ich mir eine der beiden Seiten mit n+1 aus und vereinfache, falls möglich.
Dann wende ich die Induktionsvoraussetzung an.
Dann forme ich die rechte Seite (die ja jetzt neu ist) solange um, bis ich letzenendes die rechte Seite von dem, was ich zeigen wollte raus kommt.

Dann noch: q.e.d.

So, falls das hier überhaupt richtig ist, dann komm ich i-.wie immer nur bis: IV anwenden (wenn ich das überhaupt hinkriege)... :-(

BEISPIEL:

Aufgabe: Beweise $\begin{eqnarray*} 2^{n} > n^{2} \end{eqnarray*}$

Ich bin bis jetzt so weit gekommen:

Behauptung: $\begin{eqnarray*} 2^{n} > n^{2} \end{eqnarray*}$

Startwert: no=5

Induktionsanfang (IA):

$\begin{eqnarray*} 2^{5} > 5^{2} \end{eqnarray*}$ da $\begin{eqnarray*} 32 > 25 \end{eqnarray*}$

Induktionsvoraussetzung (IV):

$\begin{eqnarray*} 2^{n} > n^{2} \end{eqnarray*}$

z.z.: $\begin{eqnarray*} 2^{n+1} > (n+1)^{2} \end{eqnarray*}$
$\begin{eqnarray*} \equiv 2^{n} * 2 > n^{2} + 2n + 1 \end{eqnarray*}$

Induktionsschluss (IS):
laut IV: $\begin{eqnarray*} 2^{n} * 2 > 2n^{2}<br /> \equiv 2^{n} + 2^{n} > n^{2} + n^{2} \end{eqnarray*}$

aber jetzt muss ich ja irgendwie solange $\begin{eqnarray*} n^{2} + n^{2} \end{eqnarray*}$ umformen, bis ich bei $\begin{eqnarray*} n^{2} + 2n + 1 \end{eqnarray*}$ wieder ankomme oder?

Ich komm da nicht weiter...

29.11.2009, 19:51

dieAnna

Auf diesen Beitrag antworten »

ich glaub ich hab das was im forum gefunden, vllt hat sich das schone erledigt^^

15.10.2013, 21:24

Dani_ela

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Hier zum Vergleich mein "Fastbeweis" von $\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$ in diesem Thread, nämlich

$\begin{eqnarray*} (n+1)^2 = n^2+\underbrace{2n+1}_{\le n^2} \le n^2+n^2=2\underbrace{n^2}_{\le 2^n}\le 2 \cdot 2^n =2^{n+1} \end{eqnarray*}$

und hier nochmals komplett, d.h., mit "ausgefüllter Lücke" (man sieht insbesondere, dass dieser Schluss nur für n>2 so funktioniert, da ich dies zwischendurch zusammen mit A(n) verwende!)

$\begin{eqnarray*} (n+1)^2 = n^2+\underbrace{2}_{<n}n+1 \le n^2+n^2\le2\underbrace{n^2}_{\le 2^n}\le 2 \cdot 2^n =2^{n+1} \end{eqnarray*}$

Das hab ich so weit verstanden. Mein Problem ist jetzt folgendes:

Wie komme ich auf $\begin{eqnarray*} 2n+1 \le n^2 \end{eqnarray*}$

bzw. $\begin{eqnarray*} n^2+\underbrace{2}_{<n}n+1 \le n^2+n^2 \end{eqnarray*}$

weil $\begin{eqnarray*} n^2+\underbrace{2}_{<n}n+1 < n^2+n^2+1 \end{eqnarray*}$

Ich hoffe ich konnte mein Problem klarmachen.
Danke schonmal für Tips und Hinweise smile

LG Daniela

16.10.2013, 08:06

Grautvornix

Auf diesen Beitrag antworten »

Zitat:

Original von Dani_ela
Das hab ich so weit verstanden. Mein Problem ist jetzt folgendes:

Wie komme ich auf $\begin{eqnarray*} 2n+1 \le n^2 \end{eqnarray*}$

Zunächst ist $\begin{eqnarray*} n\geq 3. \end{eqnarray*}$

Also gilt:

$\begin{eqnarray*} 2\cdot n+1\leq 2\cdot n+n=\underbrace{3}_{\leq n}\cdot n\leq n\cdot n=n^2 \end{eqnarray*}$

16.10.2013, 10:10

URL

Auf diesen Beitrag antworten »

alternativ kannst du dir klar machen, dass für ganze Zahlen k,l aus $\begin{eqnarray*} k<l+1 \end{eqnarray*}$ immer $\begin{eqnarray*} k\leq l \end{eqnarray*}$ folgt.

16.10.2013, 10:44

Dani_ela

Auf diesen Beitrag antworten »

Danke an euch beide. Habs verstanden Augenzwinkern

25.04.2015, 09:29

skeptiker7000

Auf diesen Beitrag antworten »

Hallo Leute,

Ich hatte ähnliche Probleme mit der Aufgabe. Ich bin bis

2n^2>=n^2+2n+1 gekommen, konnte aber keinen Weg finden diese Aussage zu beweisen. Habs hier dann gefunden und auch verstanden.

Das Problem ist, das ich das zwar verstehe aber nicht selber drauf kommen würde denke ich. Gibt es da eventuell nen "trick" oder so wie man auf diese Zwischenschritte kommt?

25.04.2015, 13:17

IfindU

Auf diesen Beitrag antworten »

Bis zu einem gewissen Grade laufen diese Art von Beweisen sehr organisch ab: Im Induktionsschritt hat man $\begin{eqnarray*} 2^{n+1} = 2 \cdot 2^n \overset{ \text{IV} }{\geq} 2 \cdot n^2 \end{eqnarray*}$ . Nun wollte man $\begin{eqnarray*} 2^{n+1} \geq (n+1)^2 \end{eqnarray*}$ zeigen, und da $\begin{eqnarray*} 2^{n+1} \geq 2 n^2 \end{eqnarray*}$ ist, reicht es also $\begin{eqnarray*} 2n^2 \geq (n+1)^2 \end{eqnarray*}$ zu zeigen, da dann $\begin{eqnarray*} 2^{n+1} \geq 2n^2 \geq (n+1)^2 \end{eqnarray*}$ ist.

Also reduziert sich das Problem auf die quadratische Ungleichung $\begin{eqnarray*} 2n^2 \geq (n+1)^2 = n^2 + 2n + 1 \end{eqnarray*}$ . Nach Umstellen bekommt man $\begin{eqnarray*} n^2 - 2n - 1 \geq 0 \end{eqnarray*}$ . Wenn man das gezeigt hat, ist man also fertig. Um das zu zeigen, kann man vieles machen. Elegant wäre $\begin{eqnarray*} n^2 - 2n - 1 = (n - 1)^2 - 2 \overset!\geq 0 \end{eqnarray*}$ zu zeigen. Alternativ berechnet man die Nullstellen des Polynoms $\begin{eqnarray*} p(x) = x^2 - 2x - 1 \end{eqnarray*}$ und argumentiert dann welches Vorzeichen die Funktion haben muss.

Was man hier gemacht hat ist einfach zu sehen: Ich will $\begin{eqnarray*} n^2 \geq 2n + 1 \end{eqnarray*}$ , und das kriege ich mit $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ mit der Kette $\begin{eqnarray*} n^2 = n \cdot n \geq 3 \cdot n = 2n + n \geq 2 n + 1 \end{eqnarray*}$ sofort hin. Das macht es natürlich sehr schön, aber man kann es wie oben auch durch Umformen zeigen.

25.04.2015, 14:42

skeptiker7000

Auf diesen Beitrag antworten »

Also das mit n^2-2n-1 > 0 verstehe ich schon, aber was genau bringt dir das jetzt, die nullstellen zu berechnen? Also die Funktion wird kleiner 0 zwischen den Nullstellen. Also gilt das ja auch nicht für alle n.

25.04.2015, 14:44

IfindU

Auf diesen Beitrag antworten »

Die Nullstellen sind aber beide kleiner 3. Und wenn die Funktion nur zwischen den Nullstellen negativ ist, und kein $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ dazu gehört, ist die Ungleichung dann für $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ erfüllt.

25.04.2015, 15:20

skeptiker7000

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Die Nullstellen sind aber beide kleiner 3. Und wenn die Funktion nur zwischen den Nullstellen negativ ist, und kein $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ dazu gehört, ist die Ungleichung dann für $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ erfüllt.

okay das ist mir klar, das habe ich auch vorher gesehen. Was mir schwer fällt, ist wie ich das jetzt mathematisch korrekt ausdrücken soll bzw aufschreiben. Also wie formuliere ich das korrekt, dass die Funktion nur zwischen den Nullstellen kleiner 0 ist und da n>3 laut definition sonst immer größer 0 ist.

25.04.2015, 15:27

IfindU

Auf diesen Beitrag antworten »

Da kann man verschiedene Methoden benutzen:
Methode 1):
-Quadratische Polynome haben höchstens 2 reelle Nullstellen
-Beim Vorzeichenwechsel haben stetige Funktionen eine Nullstelle

Methode 2):
Die Funktion ist ab der zweiten Nullstelle streng monoton wachsend. Das könnte man per Induktion zeigen, oder man bestimmt die Ableitung und sieht, dass diese überall größer gleich 0.

Das "Problem" damit ist, dass man etwas fortgeschrittene Mathematik benutzen muss. Daher sind elementare Abschätzungen in der Regel auch schöner.

25.04.2015, 15:44

Iorek

Auf diesen Beitrag antworten »

Eine sehr elementare Methode:

mit Hilfe der Linearfaktorzerlegung lässt sich das ohne Rückgriff auf Funktionen, Stetigkeit oder Differenzierbarkeit nachweisen. Sind $\begin{eqnarray*} x_1,x_2 \end{eqnarray*}$ die Nullstellen mit $\begin{eqnarray*} x_1<x_2 \end{eqnarray*}$ , so lässt sich der quadratische Ausdruck schreiben als $\begin{eqnarray*} (x-x_1)(x-x_2) \end{eqnarray*}$ . Für alle $\begin{eqnarray*} x>x_2 \end{eqnarray*}$ ist dann $\begin{eqnarray*} x-x_1>0,x-x_2>0 \end{eqnarray*}$ und das Produkt positiver Zahlen ist wieder positiv.

25.04.2015, 15:50

skeptiker7000

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Da kann man verschiedene Methoden benutzen:
Methode 1):
-Quadratische Polynome haben höchstens 2 reelle Nullstellen
-Beim Vorzeichenwechsel haben stetige Funktionen eine Nullstelle

Methode 2):
Die Funktion ist ab der zweiten Nullstelle streng monoton wachsend. Das könnte man per Induktion zeigen, oder man bestimmt die Ableitung und sieht, dass diese überall größer gleich 0.

Das "Problem" damit ist, dass man etwas fortgeschrittene Mathematik benutzen muss. Daher sind elementare Abschätzungen in der Regel auch schöner.

Hmm ja genau da sehe ich das Problem mit diesem Verfahren, also n^2-2n-1 >= 0 beweisen um wiederum den Induktionsschritt zu zeigen.
Die hier in dem thread vorher verwendete Methode zu zeigen, dass 2n+1 <= n^2 ist fand auch "besser". Ich nehme mal an das meintest du mit abschätzen ist schöner oder?

edit: wie konnte ich nicht an die linearfaktorzerlegung denken, danke!

« vorherige Seite 12

Neue Frage »

Antworten »

n^2 < 2^n per Induktion beweisen - Seite 2

Verwandte Themen