n^2 < 2^n per Induktion beweisen

14.11.2009, 07:17

SoerenC

n^2 < 2^n per Induktion beweisen

Hallo,

kann mir jemand einen Tipp geben, wie ich die Aufgabe löse:

$\begin{eqnarray*} n^2 \le 2^n \ \ \forall \ n > 3, wobei \ n \in \mathbb N \end{eqnarray*}$

Das sollen wir per Induktion beweisen. danke.

14.11.2009, 08:11

Egal

Auf diesen Beitrag antworten »

Wie weit sind denn deine eigenen Überlegungen gediehen? Hast du schon irgendwelche Ansätze? Induktionsverankerung? Den Schritt? Vielleicht die dabei entstehende quadratische Gleichung schonmal ausmultipliziert?

14.11.2009, 12:24

SoerenC

Auf diesen Beitrag antworten »

Mit Induktion habe ich soweit keine Probleme, wenn es um Reihen geht, die man mittels Formel darstellen kann. Normal setze ich mich dran und rechne einfach drauf los. Ich habe einige Zeit dran gesessen und komme nicht drauf. Für einen Ansatz wäre ich dankbar.

14.11.2009, 12:36

David_pb

Auf diesen Beitrag antworten »

Ansatz:

Wenn $\begin{eqnarray*} \forall n > 3, n \in \mathbb N | n^2 \leq 2^n \end{eqnarray*}$ gilt dann muss auch gelten: $\begin{eqnarray*} (n+1)^2 \leq 2^{n+1} \Leftrightarrow n^2 + 2n + 1 \leq 2 \cdot 2^n = 2^n + 2^n \end{eqnarray*}$

14.11.2009, 12:47

SoerenC

Auf diesen Beitrag antworten »

Daraus kann man folgern, dass $\begin{eqnarray*} 2n+1 \le 2^n \end{eqnarray*}$ sein muss. Das hilft mir für den eigentlichen Beweis nicht weiter.

14.11.2009, 12:50

David_pb

Auf diesen Beitrag antworten »

Du kannst ja auch für $\begin{eqnarray*} 2n+1 \leq 2^n \end{eqnarray*}$ einen Beweis führen, oder?

14.11.2009, 12:53

kiste

Auf diesen Beitrag antworten »

Oder du benutzt nochmal die Induktionsvorraussetzung und zeigst $\begin{eqnarray*} 2n+1\leq n^2 \end{eqnarray*}$

14.11.2009, 13:29

SoerenC

Auf diesen Beitrag antworten »

Gut, danke.

Ich würde sagen, da nun $\begin{eqnarray*} (n+1)^2 = n^2 + 2n + 1 \le 2^{n+1} \end{eqnarray*}$ , kann ich mit $\begin{eqnarray*} 2n+1 < n^2 \ \forall n > 2 \end{eqnarray*}$ zeigen, dass...ähm, ja, was eigentlich?

14.11.2009, 13:34

kiste

Auf diesen Beitrag antworten »

Das zusammenfügen der Teile überlegst du dir lieben selbst noch einmal. Da lernst du viel mehr als wenn wir es dir jetzt vorsagen.

14.11.2009, 13:42

SoerenC

Auf diesen Beitrag antworten »

da nun $\begin{eqnarray*} (n+1)^2 = n^2 + 2n + 1 \le 2^{n+1} \end{eqnarray*}$ , kann ich mit $\begin{eqnarray*} 2n+1 < n^2 \ \forall n > 2 \end{eqnarray*}$ zeigen, dass damit auch $\begin{eqnarray*} 2n+1 < 2^n \end{eqnarray*}$ gilt.

Wie hilft mir das weiter, wenn ich beweisen will, dass $\begin{eqnarray*} n^2 \le 2^n \end{eqnarray*}$ ?

14.11.2009, 13:46

kiste

Auf diesen Beitrag antworten »

Du gehst das falschrum an. Du weißt bereits dass $\begin{eqnarray*} n^2 \leq 2^n \end{eqnarray*}$ ist und willst jetzt herausfinden dass $\begin{eqnarray*} (n+1)^2 \leq 2^{n+1} \end{eqnarray*}$ ist.
Dazu schätzst du ab:
$\begin{eqnarray*} n^2 + 2n + 1 \leq ... \end{eqnarray*}$
Und jetzt für ... eben die beiden Ungleichungen benutzen die du bereits zur Hand hast

14.11.2009, 14:03

SoerenC

Auf diesen Beitrag antworten »

Eigentlich weiß ich es nur für ein bestimmtes $\begin{eqnarray*} n \end{eqnarray*}$ , das ich ausprobiert habe. $\begin{eqnarray*} n^2 \le 2^n \end{eqnarray*}$ will ich ja beweisen.

$\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$ muss ich zeigen.

Probier ich es Mal.

Ich muss zeigen, dass $\begin{eqnarray*} n^2 + 2n + 1 \le 2^{n+1} \ \ \ \ \ (2^{n+1} = 2 \cdot 2^n = 2^n + 2^n) \end{eqnarray*}$ .

Ich kann bisher nur zeigen, dass $\begin{eqnarray*} 2n +1 < n^2 \ \ \ \forall \ n > 2 \end{eqnarray*}$ . (weil ist offensichtlich)

Wenn ich nun gezeigt habe, dass $\begin{eqnarray*} 2n +1 < n^2 \end{eqnarray*}$ , habe ich noch nicht gezeigt, dass auch $\begin{eqnarray*} n^2 \le 2^n \end{eqnarray*}$

14.11.2009, 14:14

kiste

Auf diesen Beitrag antworten »

Nochmal:
Du nimmst an dass $\begin{eqnarray*} n^2 \leq 2^n \end{eqnarray*}$ bereits bewiesen ist, das ist gerade dein $\begin{eqnarray*} A(n) \end{eqnarray*}$ !

Okay jetzt benutze einmal $\begin{eqnarray*} 2n+1 < n^2 \end{eqnarray*}$ (das man auch noch beweisen muss, da reicht aber eine Funktionsuntersuchung aus der Schule) um $\begin{eqnarray*} n^2 + 2n + 1 < ... \end{eqnarray*}$ anzuschätzen

14.11.2009, 14:24

SoerenC

Auf diesen Beitrag antworten »

ich verstehe es nicht. Bitte gib mir die Lösung.
Weitere 3 Stunden will ich nicht an der Aufgabe sitzen. Ich muss auch andere Sachen lernen. Manchmal fällt der Groschen erst, wenn man es sieht. Wäre nett, danke.

14.11.2009, 14:31

kiste

Auf diesen Beitrag antworten »

Nein, so kurz vor dem Ziel werd ich es dir nicht verraten.
Du sollst die mit Hilfe der Ungleichung $\begin{eqnarray*} 2n + 1 \leq n^2 \end{eqnarray*}$
$\begin{eqnarray*} n^2 + 2n + 1 \leq ... \end{eqnarray*}$ abschätzen.
Auch wenn es extremstes Schulwissen ist sage ich dir:
$\begin{eqnarray*} a+b \leq a + c \end{eqnarray*}$ falls $\begin{eqnarray*} b \leq c \end{eqnarray*}$ . Hier: a=n^2,b=2n+1, c=n^2.
Einsetzen und dann Induktionsvorraussetzung benutzen und du bist schon fertig

14.11.2009, 14:37

SoerenC

Auf diesen Beitrag antworten »

ok, wenn es sein muss. welche vorteile es bringt, entgeht mir aber. Für mich ist der Effekt der Gleiche zwischen Lösung selbst erarbeiten und Lösungsweg sehen. Abgesehen, dass ich weitere Zeit in diese blöde Aufgabe setzen muss, weil Du es so willst (ist nicht böse gemeint). (vielleicht sollte ich einfach mal pause machen)

Ist die zweite Zeile von Dir oben korrekt?

14.11.2009, 15:08

kiste

Auf diesen Beitrag antworten »

Korrekt ja, aber ich hab zur besseren Lesbarkeit noch eine neue Zeile eingefügt. Eine Pause ist sicherlich eine gute Idee, wie gesagt: Wir bewegen uns gerade auf dem Niveau der 7. Klasse

14.11.2009, 22:26

Mystic

Auf diesen Beitrag antworten »

Hier als "Pausenfüller" und außer Konkurrenz, da nicht induktiv, der wohl eleganteste Beweis der in Rede stehenden Behauptung (allerdings nur für n>4, der Fall n=4 muss manuell geprüft werden):

$\begin{eqnarray*} n^2=\binom n1 +\binom n2+ \binom n{n-2}<(1+1)^n=2^n \end{eqnarray*}$

14.11.2009, 22:41

kiste

Auf diesen Beitrag antworten »

hübsch

14.11.2009, 23:35

Matheversteher

Auf diesen Beitrag antworten »

So ich möchte dann mal weiter machen. Auch ich stehe vor diesem Problem, mit diesem Beweis.

Zitat:

Original von Kiste
Nein, so kurz vor dem Ziel werd ich es dir nicht verraten. Du sollst die mit Hilfe der Ungleichung $\begin{eqnarray*} 2n + 1 \leq n^2 \end{eqnarray*}$ $\begin{eqnarray*} n^2 + 2n + 1 \leq ... \end{eqnarray*}$ abschätzen. Auch wenn es extremstes Schulwissen ist sage ich dir: $\begin{eqnarray*} a+b \leq a + c \end{eqnarray*}$ falls $\begin{eqnarray*} b \leq c \end{eqnarray*}$ . Hier: a=n^2,b=2n+1, c=n^2. Einsetzen und dann Induktionsvorraussetzung benutzen und du bist schon fertig

Also wenn ich das mal fortführe, dann steht da, dass
$\begin{eqnarray*} n^2+2n+1 \leq n^2 + n^2 \end{eqnarray*}$ falls $\begin{eqnarray*} 2n+1 \leq n^2 \end{eqnarray*}$ ist.

Aber auch mir hilft das nicht sonderlich viel weiter.
Ich weis aus der Schule noch, dass eine Exponwentialfunktion ( $\begin{eqnarray*} 2^n \end{eqnarray*}$ ) im Unendlichen schneller wächst als eine "normale" Funktion ( $\begin{eqnarray*} n^2+2n+1 \end{eqnarray*}$ ).
Von daher muss $\begin{eqnarray*} 2^n \end{eqnarray*}$ ab einem gewissen Wert für $\begin{eqnarray*} n \in N \end{eqnarray*}$ größer sein als $\begin{eqnarray*} n^2+2n+1 \end{eqnarray*}$

Mhh was ich jetzt nocht so richtig verstehe ist die Induktionsvorraussetzung? ist das das $\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$ ?

Wenn das so ist, dann müsste ich das hier so machen

$\begin{eqnarray*} (n+1)^2+2(n+1)+1 \leq (n+1)^2 + (n+1)^2 \end{eqnarray*}$ (ist die Formel aus dem zitat nun mit $\begin{eqnarray*} n=n+1 \end{eqnarray*}$ )
Dann erhalte ich folgendes:
$\begin{eqnarray*} n^2+2n+1+2n+2+1\leq 2*(n^2+2n+1) \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} n^2+2n =n^2+2n+1 \end{eqnarray*}$ und $\begin{eqnarray*} 2n+3 < n^2+2n+1 \end{eqnarray*}$

Wobei dann die rechte Seite in $\begin{eqnarray*} n^2+2n+1+2n+2+1\leq 2*(n^2+2n+1) \end{eqnarray*}$ größer sein muss als die linke für $\begin{eqnarray*} n\geq5 \end{eqnarray*}$
Ist es das oder habe ich mir jetzt hier irgendwas wild zusammen gereimt Erstaunt2

15.11.2009, 02:55

SoerenC

Auf diesen Beitrag antworten »

Was bringt mir die Aussage $\begin{eqnarray*} n^2 + (2n+1) \le n^2 + n^2 \end{eqnarray*}$ wie von Algebraiker auf der vorherigen Seite angedeutet?

Ich sitze seit 3 Tagen viele Stunden an dieser Aufgabe wegen 2 von 20 Punkten. Und nun ist es manchmal so, dass man den Baum nicht sieht, obwohl er direkt vor einem steht. Ein Induktionsbeweis kann ja nicht so schwierig sein.

Also, ich werde definitiv keine weitere Minute mir an dieser Aufgabe den Kopf zerbrechen.

Über die Lösung jedoch ja.

Es ist effizienter eine Lösung nachzuvollziehen in wenigen Minuten als über Stunden zu versuchen, selbst drauf zu kommen.

Falls mir niemand die Lösung geben will, weil es ja sooo wichtig ist, dass ich es selbst löse, dann habe ich sie eben nicht. (wäre niemanden böse. aber ich handle so nicht)

15.11.2009, 04:01

SoerenC

Auf diesen Beitrag antworten »

Also gut, ich habe es jetzt so aufgeschrieben, aber das gefällt mir nicht:

zu zeigen: $\begin{eqnarray*} n^2 \le 2^n \end{eqnarray*}$

$\begin{eqnarray*} n=1\ \ \ \ \ \ 1 \le 2 \end{eqnarray*}$
$\begin{eqnarray*} n=2\ \ \ \ \ \ 4 \le 4 \end{eqnarray*}$
$\begin{eqnarray*} n=3\ \ \ \ \ \ 9 \le 8 \end{eqnarray*}$
$\begin{eqnarray*} n=4\ \ \ \ 16 \le 16 \end{eqnarray*}$
$\begin{eqnarray*} n=5\ \ \ \ 25 \le 32 \end{eqnarray*}$

Ab n=4 ist das exponentielle Wachstum stets stärker als das lineare.

Da nun $\begin{eqnarray*} A(n) \end{eqnarray*}$ gezeigt ist für gewisse $\begin{eqnarray*} n \end{eqnarray*}$ , folgere ich, dass auch $\begin{eqnarray*} A(n+1) \end{eqnarray*}$ gilt:

$\begin{eqnarray*} (n+1)^2 \le 2^{n+1} \end{eqnarray*}$
$\begin{eqnarray*} (n^2 + 2n +1) \le 2 \cdot 2^n \end{eqnarray*}$
$\begin{eqnarray*} (n^2 + 2n +1) \le 2^n + 2^n \Leftrightarrow (\ n^2 \le 2^n\ ) \wedge (\ 2n + 1 \le 2^n\ ) \end{eqnarray*}$

$\begin{eqnarray*} n^2 \le 2^n \end{eqnarray*}$ ist bereits gezeigt und $\begin{eqnarray*} (\ 2n + 1 \le 2^n\ )\ \forall \ n > 2 \end{eqnarray*}$ ist offensichtlich.

$\begin{eqnarray*} \Rightarrow (n^2 + 2n + 1) = (n + 1)^2 \le 2^{n+1}\ \forall \ n > 3 \end{eqnarray*}$

Hätte ich mit n=2 angefangen, wäre die Induktion nämlich nicht korrekt gewesen.

Also muss ich noch zeigen, warum es erst für alle n > 3 gilt.

15.11.2009, 08:00

Mystic

Auf diesen Beitrag antworten »

Das Problem besteht u.a. auch darin, dass dir offensichlich nicht klar ist, wie ein Beweis mit vollständiger Induktion im Prinzip funkioniert... Wenn A(n) die Induktionsaussage ist, in diesem Beispiel also

$\begin{eqnarray*} A(n) :\Leftrightarrow n^2\le 2^n, \quad (n \ge 4) \end{eqnarray*}$

dann ist es im Induktionsschluß verboten, so wie du es machst, einfach A(n+1) zu betrachten und so lange umzuformen, bis man auf eine wahre Aussage kommt... Selbst wenn es sich dabei um Äquivalenzumformungen ist das ein ganz schlechter Stil und diese scheinbar nicht auszurottende Unart ist schärfstens abzulehnen, so auch hier...

Wenn du also

$\begin{eqnarray*} 2n+1 \le n^2 \quad (n \ge 4) \end{eqnarray*}$

schon bewiesen hast (wann beweist du das endlich???), dann geht der korrekte Beweis von A(n+1), unter der Voraussetzung, dass A(n) gilt, so weiter

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

Wie gesagt, wann beweist du endlich

$\begin{eqnarray*} 2n+1 \le n^2 \quad (n \ge 4) \end{eqnarray*}$

was nach dem was du schreibst eh "offensichtlich", aber eben noch immer das "missing link" hier ist? verwirrt

15.11.2009, 12:49

SoerenC

Auf diesen Beitrag antworten »

OK, könnte ich bitte eine korrekte Lösung sehen? Es ist mttlerweile Tag Nr. 3.

15.11.2009, 12:51

kiste

Auf diesen Beitrag antworten »

Die Lösung wurde dir aber schon gegeben!!! geschockt

Mystic hat die komplette Aufgabe jetzt(bis auf die für dich offensichtliche Aussage) gelöst.
Wenn du wirklich etwas lernen willst dann musst du dafür arbeiten

15.11.2009, 12:55

SoerenC

Auf diesen Beitrag antworten »

Ich arbeite schon seit drei Tagen an dieser Aufgabe. Alle anderen Induktionsaufgaben von dem Blatt habe ich perfekt gelöst. Nur eben diese eine einzige Aufgabe kann ich nicht. Bitte eine korrekte Lösung. Wenn nicht, dann lasst es eben. Ich sitze seit Tagen und es scheint, als wäre ich hier irgendwie blockiert.

15.11.2009, 13:08

kiste

Auf diesen Beitrag antworten »

Fang an die Beiträge richtig zu lesen!
Die Lösung steht bereits in einem der Beiträge!!!

15.11.2009, 13:11

SoerenC

Auf diesen Beitrag antworten »

vielen dank. ich habe bereits mehrere mal gesagt, dass ich es bei dieser aufgabe einfach nicht sehe. würde sagen, lassen wir es. auf rätselraten habe ich mittlerweile keinen bock mehr. trotzdem danke. ciao.

15.11.2009, 15:37

SoerenC

Auf diesen Beitrag antworten »

Schade, dass es hier tatsächlich niemanden zu geben scheint, der mich hier "an die Hand nimmt" und die Sache Schritt für Schritt mit mir durchgehten will. Könnt Euch glücklich schätzen. Du hast sicher nie auf dem Schlauch gestanden, hast immer alles ganz alleine gemacht. Bravo!

15.11.2009, 15:47

kiste

Auf diesen Beitrag antworten »

Du hast vorgeschlagen es zu lassen, oder etwa nicht?
Ich helfe dir gerne, du musst nur sagen was genau du nicht verstehst in den Beiträgen die dir bereits gegeben wurden. Wie gesagt die Lösung wurde bereits gepostet. Wenn du sie nicht verstehst musst du eben sagen wo und was du nicht verstehst.
Ich und hoffentlich auch sonst keiner werde dir nicht deine Abgabe formulieren.

Natürlich schaffe ich auch nicht alles, aber wenn ich etwas nicht schaffe dann verlange ich auch nicht dass mir jemand die Lösung gibt. Entweder ich schaffe es, wenn auch mit Hilfe, oder ich schaffe es eben nicht(was wahrscheinlich bei mind. 1 WT-Aufgabe morgen der Fall sein wird da ich zu viel Zeit hier versurfe Big Laugh

15.11.2009, 15:52

SoerenC

Auf diesen Beitrag antworten »

Ich möchte einfach die Lösung sehen. Mehr nicht. Ich habe mich damit beschäftigt und komme nicht drauf. Warum, weiß ich nicht. Vielleicht bringt es was, wenn ich die Lösung sehe. Ganz einfach ohne Rätselraten zu müssen. Bisher habe ich alles verstanden. Wo es hier hakt, weiß ich nicht, habe ich aber auch schon gesagt. Ist das denn so schwierig. Warum soll ich mir noch weiter von anderen diktieren lassen, "Finde es selbst raus"? Im Studium ist es eben so, dass man nicht alles Aufgaben eines Übungsblattes lösen kann. Deshalb wird man zu gemeinschaftlichen Arbeit (Arbeitsteilung) angeregt. Hier aber kommt es mir so vor, als soll man alles doch allein machen, was nicht zu schaffen ist. Einfach nur die Lösung. Wenn ich sie dann gesehen habe, werde ich auch sagen, wo das Problem bei mir gelegen hat. Das wäre nett. Aber der Frust hier "Finde es selbst raus!", frustet mehr, als die eine Aufgabe. Nicht böse sein. Aber einfach nur die Lösung. Bitte. Ich sitze seit 3 TAGEN an dieser Aufgabe!!

15.11.2009, 15:58

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von BaldrianForte
Eigentlich weiß ich es nur für ein bestimmtes $\begin{eqnarray*} n \end{eqnarray*}$ , das ich ausprobiert habe.

(hoffentlich war das n=4)

Zitat:

Original von Mystic
Wenn du also

$\begin{eqnarray*} 2n+1 \le n^2 \quad (n \ge 4) \end{eqnarray*}$

schon bewiesen hast [...] dann geht der korrekte Beweis von A(n+1), unter der Voraussetzung, dass A(n) gilt, so weiter

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

15.11.2009, 16:03

SoerenC

Auf diesen Beitrag antworten »

Ja, schon, aber da steht noch nicht, warum $\begin{eqnarray*} n^2 \le 2^n \end{eqnarray*}$ ist.

15.11.2009, 16:05

kiste

Auf diesen Beitrag antworten »

Endlich eine konkrete Frage. Das hättest du auch viel früher haben können.

Du willst das ganze doch aus A(n) folgern. Also nimmst du an dass A(n) gilt.
A(n) ist aber gerade die Aussage $\begin{eqnarray*} n^2 \leq 2^n \end{eqnarray*}$ .

15.11.2009, 16:11

SoerenC

Auf diesen Beitrag antworten »

Ja. Aber, wenn ich eine Formel nicht kenne und sie ausprobiere für n=2 beispielsweise, dann geht die Induktion in diesem Fall schief, weil die Ungleichung für n=3 nicht zutrifft. Ich will wissen, warum die Ungleichung für alle n>3 zutrifft und warum sowas wie bei n=3 nicht noch Mal passieren kann, solange n>3.

Ansonsten ist der Beweis unvollständig. Ich will nicht einfach behaupten, dass die Ungleichung für alle n>3 gilt, sondern will sogar das beweisen.

15.11.2009, 16:16

kiste

Auf diesen Beitrag antworten »

Das Prinzip der Induktion ist doch:
Wir zeigen es für einen Start, hier hast du n=4 gewählt, und dann zeigen wir dass es für alle Nachfolger gilt. Also:
Wenn es für A(n) gilt, dann gilt es auch für A(n+1).
D.h. die Behauptung dass es für A(n) gilt ist gesichert dadurch dass wir es für ein n bewiesen haben.

Der Beweis für eine Zahl n ginge dann so(log. gesehen):
Wir wissen es gilt für 4, außerdem wissen wir es gilt für jeden Nachfolger, also dann auch für 5. Da es jetzt für 5 gilt, gilt es auch für 6. Usw. bis du bei der Zahl angekommen bist die du haben willst

Der Beweis ginge nicht durch wenn wir mit n=1 oder so starten, weil in diesem Fall die benutze Ungleichung $\begin{eqnarray*} 2n+1\leq n^2 \end{eqnarray*}$ noch nicht stimmt.

15.11.2009, 16:22

SoerenC

Auf diesen Beitrag antworten »

Danke, für die Mühe.
Vielleicht reden wir aneinander vorbei.
Naütürlich habe ich es für n=4 geprüft. Aber die Ungleichung hat auch schon für n=1 und n=2 gestimmt. Demnach kann ich die Induktion bereits für n=1 zeigen. Woher soll ich denn $\begin{eqnarray*} \rightarrow \end{eqnarray*}$ wissen $\begin{eqnarray*} \leftarrow \end{eqnarray*}$ , dass es für irgendein n>2 nicht gilt? Ein normaler Mensch prüft die Ungleichung für n=1, vielleicht auch für n=4 und n=5 und denkt sich wird schon passen. Nun, bei n=3 passt es eben nicht. Somit ist die Induktion, wenn man sie für n=1 oder n=2 zeigt, ungültig und hat es nicht einmal gemerkt. Nun muss ich also beweisen, dass mir das bei einem n>3 nicht nochmal passieren kann.

15.11.2009, 16:27

kiste

Auf diesen Beitrag antworten »

In deinem Beweis benutzt du doch in essentieller Weise dass n>=3 ist, denn sonst wäre nicht 2n+1 <= n^2
n=1: 3 <= 1
n=2: 5 <= 4

Würdest du also bei n=1 oder n=2 die Induktion beginnen so könntest du die Abschätzung nicht machen und der Beweis der Folgerung käme erst gar nicht zu stande!
Da der Beweis von A(n) => A(n+1) aber für n>=3 funktioniert, stimmt auch der Beweis den wir seit 3 Seiten diskutieren Augenzwinkern

15.11.2009, 16:36

SoerenC

Auf diesen Beitrag antworten »

Davon rede ich ja die ganze Zeit. Der Beweis geht für n<3 nicht. Woher weiß ich, dass er für alle n>3 gilt? Woher weiß ich, dass gerade n=4 die unterste Grenze für n ist? Das kann jeder behaupten.

Der Prof könnte mich auch reinlegen und n=4 ist nicht die unterste Grenze für die Gültigkeit der Ungleichung, sondern ein n>4. Er hätte auch sagen können, die Ungleichung gilt für alle n>0. Ich hätte es für n=1 geprüft und die Ungültigkeit für n=3 gar nicht gemerkt.

15.11.2009, 16:39

kiste

Auf diesen Beitrag antworten »

Lese doch einmal genau was ich schreibe geschockt

Unser Beweis funktioniert ab n=4. Dort ist alles schön weil wir es bewiesen haben.(Wenn hier das Problem liegt musst du genau nachfragen was an dem Beweis unklar ist! Mir kommt es so vor als ob du große Probleme damit hast Induktion zu verstehen - im Widerspruch zu deiner Behauptung alle anderen Induktionsaufgaben leicht gelöst zu haben)
Jetzt könnte es natürlich sein dass es für n=3 auch gilt, das widerlegen wir aber durch einfaches einsetzen.

Ergo haben wir es nicht nur behauptet, sondern auch bewiesen!

12 nächste Seite »

Neue Frage »

Antworten »

n^2 < 2^n per Induktion beweisen

Verwandte Themen