Vollständige Induktion

22.10.2008, 16:48

Svenja1986

Auf diesen Beitrag antworten »

Vollständige Induktion

Aufgabe:

(a) Bestimmen Sie bitte durch Ausprobieren ein minimales $\begin{eqnarray*} n_{0} \in \mathbb N_{0} \end{eqnarray*}$ so, dass $\begin{eqnarray*} 3^{n} > n^{3} \end{eqnarray*}$ für alle $\begin{eqnarray*} n \leq n_{0} \end{eqnarray*}$ und formulieren Sie bitte diese Aussage mit Hilfe von Quantoren.

(b) Bitte beweisen Sie (a) mit vollständiger Induktion.

Soooooo Big Laugh

Big Laugh

Also, die a hab ich.
Ich vermute $\begin{eqnarray*} n_{0} = 4 \end{eqnarray*}$ als minimalen Induktionsbeginn.
Behauptung in Quantorenschreibweise:

$\begin{eqnarray*} A(n): \forall n \geq 4: 3^{n} > n^{3} \end{eqnarray*}$

Jetzt die b:

Induktionsverankerung: Die Aussage A(4) ist wahr, da

$\begin{eqnarray*} 4^{3} = 64 < 81 = 3^{4} \end{eqnarray*}$ ist.

Induktionsschritt:

Die Aussage A(n) gelte für ein beliebiges $\begin{eqnarray*} n_{0} \in \mathbb N_{0} \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ . Dann ist:

$\begin{eqnarray*} 3^{n+1} = 3^{n} \cdot 3 \geq n^{3} \cdot 3 = 3 \cdot n^{3} \geq (n + 1)^{3}. \end{eqnarray*}$

Richtig bis jetzt? Wie mache ich nun weiter? verwirrt

verwirrt

22.10.2008, 16:54

Zizou66

Auf diesen Beitrag antworten »

Multipliziere $\begin{eqnarray*} (n+1)^3 \end{eqnarray*}$ aus, dann wird es einfach...

Edit: Außerdem sieht hier etwas nicht gut aus, schreib es doch so:

Induktionsschlus:

$\begin{eqnarray*} 3^{n+1}> (n+1)^3 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow 3^n\cdot 3 > (n+1)^3 \end{eqnarray*}$

22.10.2008, 16:58

Svenja1986

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
$\begin{eqnarray*} n^{3} + 2n^{2} + n \end{eqnarray*}$

Was mache ich jetzt damit?

22.10.2008, 16:59

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Svenja1986
so, dass $\begin{eqnarray*} 3^{n} > n^{3} \end{eqnarray*}$ für alle $\begin{eqnarray*} n \leq n_{0} \end{eqnarray*}$

Hier meinst du sicher $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ statt $\begin{eqnarray*} n \leq n_{0} \end{eqnarray*}$ !

22.10.2008, 17:00

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von Zizou66

Edit: Außerdem sieht hier etwas nicht gut aus, schreib es doch so:

Induktionsschlus:

$\begin{eqnarray*} 3^{n+1}> (n+1)^3 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow 3^n\cdot 3 > (n+1)^3 \end{eqnarray*}$

Warum nur noch "größer" und nicht mehr "größer-gleich"?

22.10.2008, 17:01

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von Svenja1986
so, dass $\begin{eqnarray*} 3^{n} > n^{3} \end{eqnarray*}$ für alle $\begin{eqnarray*} n \leq n_{0} \end{eqnarray*}$

Hier meinst du sicher $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ statt $\begin{eqnarray*} n \leq n_{0} \end{eqnarray*}$ !

Jap stimmt. Falsch abgeschrieben...

Anzeige

22.10.2008, 17:01

Zizou66

Auf diesen Beitrag antworten »

Nein, das ist nicht richtig.

$\begin{eqnarray*} (n+1)^3=(n+1)\cdot (n+1)\cdot (n+1) \end{eqnarray*}$

Versuchs nochmal...

22.10.2008, 17:03

tmo

Auf diesen Beitrag antworten »

Man kann es auch ellegant ohne ausmultiplizieren machen Augenzwinkern

Augenzwinkern

Es ist $\begin{eqnarray*} 3 \geq \left(1+\frac{1}{4} \right)^3 \geq \left(1+\frac{1}{n} \right)^3 \end{eqnarray*}$

Also $\begin{eqnarray*} 3n^3 \geq ... \end{eqnarray*}$

22.10.2008, 17:05

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Man kann es auch ellegant ohne ausmultiplizieren machen Augenzwinkern

Augenzwinkern

Es ist $\begin{eqnarray*} 3 \geq \left(1+\frac{1}{4} \right)^3 \geq \left(1+\frac{1}{n} \right)^3 \end{eqnarray*}$

Also $\begin{eqnarray*} 3n^3 \geq ... \end{eqnarray*}$

Das kann ich jetzt grad nicht nachvollziehen verwirrt

verwirrt

22.10.2008, 17:06

tmo

Auf diesen Beitrag antworten »

Dann geh erstmal den Weg von Zizou. Um den Weg können wir uns ja danach kümmern. Ich bin dann erstmal raus aus dem Thread, bis das Problem auf dem andern Weg gelöst ist.

22.10.2008, 17:10

Zizou66

Auf diesen Beitrag antworten »

Gut dann machen wir es so, ich finde das auch für den Anfang einfacher zu verstehen. Finde deinen Ansatz sehr elegant und daher wird Svenja sich auch freuen, wenn sie das gezeigt bekommt Freude

Freude

Edit: Danke Jacques Augenzwinkern

Augenzwinkern

Hab heute Deutschklausur geschrieben und lebe meine Freiheit Fehler zu machen nun wieder aus Big Laugh

Big Laugh

22.10.2008, 17:35

Jacques

Auf diesen Beitrag antworten »

[Off-Topic: ELEGANT, mit einem L. Augenzwinkern

Augenzwinkern

]

22.10.2008, 17:38

marodeur

Auf diesen Beitrag antworten »

[auch off topic: diese Aufgabe habe ich gerade gestern in meinem Tutorium als Beispiel genommen... Zufälle gibts?]

Zur Aufgabe: Die Induktion mehrmals anwenden.

22.10.2008, 17:54

Svenja1986

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
So, hab grad mal ne kurze Pause eingelegt, damit ich wieder klar denken kann...
Also, ausmultiplizieren:

$\begin{eqnarray*} n^{3} + 3n^{2} + 3n + 1 \end{eqnarray*}$

Wie gehts jetzt weiter?

22.10.2008, 18:00

Zizou66

Auf diesen Beitrag antworten »

Das ist richtig Freude

Freude

Nun was denkst du denn, wie es weiter geht? Wir haben nun die Ungleichung:

$\begin{eqnarray*} 3^n\cdot 3 > n^3+3n^2+3n+1 \end{eqnarray*}$

22.10.2008, 18:06

Svenja1986

Auf diesen Beitrag antworten »

Genau so, hab ichs grad eben hier auf en Blatt Papier geschrieben Tanzen

Tanzen

Aber ich muss ehrlich sagen: Keine Ahnung, was jetzt... verwirrt

verwirrt

Durch 3 teilen?

22.10.2008, 18:10

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Zizou66
Das ist richtig Freude

Freude

Nun was denkst du denn, wie es weiter geht? Wir haben nun die Ungleichung:

$\begin{eqnarray*} 3^n\cdot 3 > n^3+3n^2+3n+1 \end{eqnarray*}$

Hier mische ich mich doch noch mal kurz ein.

So "scharf" muss man nämlich gar nicht abschätzen. Es reicht
$\begin{eqnarray*} 3^n\cdot 3 \geq n^3+3n^2+3n+1 \end{eqnarray*}$ . Denn das "echt größer" steckt ja schon in der Induktionsvorraussetzung. Hier macht es zwar keinen Unterschied, aber es gibt bestimmt auch Induktionsbeweise, wo man die Gleichheit nicht ohne weiteres ausschließen kann.

22.10.2008, 19:18

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Es reicht $\begin{eqnarray*} 3^n\cdot 3 \geq n^3+3n^2+3n+1 \end{eqnarray*}$ .

Nein, denn das ist nicht die Induktionsbehauptung.

22.10.2008, 19:45

Svenja1986

Auf diesen Beitrag antworten »

Was denn dann? Hilfe

Hilfe

*verwirrung* traurig

traurig

22.10.2008, 19:48

Jacques

Auf diesen Beitrag antworten »

@ Svenja1986:

In der Behauptung steht $\begin{eqnarray*} > \end{eqnarray*}$ und nicht $\begin{eqnarray*} \geq \end{eqnarray*}$

22.10.2008, 19:49

Svenja1986

Auf diesen Beitrag antworten »

Ok, wie mach ich da jetzt weiter?
Was muss am Ende da stehen?

22.10.2008, 20:34

Romaxx

Auf diesen Beitrag antworten »

Hallo Svenja1986,

ich weiss nicht wie Zizou66 weitermachen würde, aber da er nicht da ist, kann ich dir meinen Weg der Lösung näher bringen.
Wir machen an einer Stelle weiter, die dir schon bekannt ist.

$\begin{eqnarray*} 3^{n+1} = 3\cdot 3^{n} > 3\cdot n^{3}=n³+n³+n³ \geq\cdots \geq n³+3n²+3n+1= (n + 1)^{3}. \end{eqnarray*}$

Da wo die Punkte sind, müssen wir nun so abschätzen, das jedem der die Ungleichungskette betrachtet, die Sache logisch erscheint.

Du hast in deinen Voraussetzungen eine Information gegeben, die dir hier weiterhilft.

$\begin{eqnarray*} n\geq 4 \end{eqnarray*}$

Das lässt sich umformen zu

$\begin{eqnarray*} n³\geq 4n² \end{eqnarray*}$

Nun kannst du in der Ungleichungskette oben, zwei der drei $\begin{eqnarray*} n³ \end{eqnarray*}$ ersetzen.

$\begin{eqnarray*} 3^{n+1} = 3\cdot 3^{n} > 3\cdot n^{3}=n³+n³+n³ \geq n³+4n²+4n²=n³+8n² \geq \dots \geq n³+3n²+3n+1= (n + 1)^{3}. \end{eqnarray*}$

Nun mache das gleiche mit $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ für $\begin{eqnarray*} n² \end{eqnarray*}$ und ersetze sinnvoll . Danach das Gleiche nocheinmal für $\begin{eqnarray*} n \end{eqnarray*}$ und du kannst deine Kette schließen.

22.10.2008, 20:48

Svenja1986

Auf diesen Beitrag antworten »

Das heißt, es würde jetzt so weiter gehen:

$\begin{eqnarray*} n²\geq 4n \end{eqnarray*}$

und dann

$\begin{eqnarray*} n\geq 4 \end{eqnarray*}$

??

22.10.2008, 21:01

Romaxx

Auf diesen Beitrag antworten »

Ja, ersetze nun die $\begin{eqnarray*} n² \end{eqnarray*}$ so, dass nur noch $\begin{eqnarray*} 3n² \end{eqnarray*}$ übrig bleibt.
Dann das gleiche für $\begin{eqnarray*} n \end{eqnarray*}$ , sodass du ebenfalls $\begin{eqnarray*} 3n \end{eqnarray*}$ übrig lässt. Wenn du das hast, sollte eine sinnvolle Abschätzung möglich sein.

22.10.2008, 21:01

Svenja1986

Auf diesen Beitrag antworten »

Ergibt irgendwie keinen Sinn bei mir unglücklich

unglücklich

22.10.2008, 21:02

Svenja1986

Auf diesen Beitrag antworten »

Was soll ich denn da alles ersetzen... das versteh ich grad nicht

22.10.2008, 21:09

Romaxx

Auf diesen Beitrag antworten »

Ich habe es dir doch eben mit $\begin{eqnarray*} n³ \end{eqnarray*}$ vorgemacht.

In der Ungleichungskette habe ich zwei der drei $\begin{eqnarray*} n³ \end{eqnarray*}$ durch $\begin{eqnarray*} 4n² \end{eqnarray*}$ ersetzt (natürlich mit der Abschätzung größer gleich).

Das gleiche Prinzip funktioniert bei den $\begin{eqnarray*} n² \end{eqnarray*}$ und bei $\begin{eqnarray*} n \end{eqnarray*}$ .

Versuche das so weiterzuführen, sodass du auf einen ähnlichen Ausdruck wie dem vorletzten Term in der Ungleichungskette gelangst. Das einzige was diese beiden Terme dann noch unterscheiden sollte, sind natürliche Zahlen, was dir ermöglicht die Kette zu schließen.

22.10.2008, 21:15

Svenja1986

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 3^{n+1} = 3\cdot 3^{n} > 3\cdot n^{3}=n³+n³+n³ \geq n³+8n² = n³ + 32n \geq \dots \geq n³+3n²+3n+1= (n + 1)^{3}. \end{eqnarray*}$

So? verwirrt

verwirrt

Wo sollen denn da noch 3 übrig bleiben?

22.10.2008, 21:22

Romaxx

Auf diesen Beitrag antworten »

Nein so nicht, du solltest $\begin{eqnarray*} 3n² \end{eqnarray*}$ übrig lassen und außerdem gehört danach kein gleich sondern ein größergleich. (du willst auf einen ähnlichen Ausdruck wie dem vorletzten Term gelangen):

$\begin{eqnarray*} 3^{n+1} = 3\cdot 3^{n} > 3\cdot n^{3}=n³+n³+n³ \geq n³+8n² \geq n³ + 3n²+ 20n \geq \dots \geq n³+3n²+3n+1= (n + 1)^{3}. \end{eqnarray*}$

Und nun nocheinmal für das $\begin{eqnarray*} n \end{eqnarray*}$ .

22.10.2008, 21:27

Svenja1986

Auf diesen Beitrag antworten »

AAAHHHH, jetzt hab ichs verstanden Tanzen

Tanzen

Wenn ich das dann für das $\begin{eqnarray*} n \end{eqnarray*}$ gemacht habe, komme ich auf:

$\begin{eqnarray*} 3^{n+1} = 3\cdot 3^{n} > 3\cdot n^{3}=n³+n³+n³ \geq n³ + 3n²+ 20n \geq n³ + 3n²+ 3n + 68 \geq \dots \geq n³+3n²+3n+1= (n + 1)^{3}. \end{eqnarray*}$

So, und was sagt mir das jetzt verwirrt

verwirrt

22.10.2008, 21:32

Romaxx

Auf diesen Beitrag antworten »

Die Punkte in der Kette brauchst du nun nicht mehr.

$\begin{eqnarray*} 3^{n+1} = 3\cdot 3^{n} > 3n^{3}\geq n³ + 8n² \geq n³ + 3n²+ 20n \geq n³ + 3n²+ 3n + 68 \geq n³+3n²+3n+1= (n + 1)^{3}. \end{eqnarray*}$

Die ist ein sinnvolle Abschätzung, die deinen Induktionsschluss darstellt.
Natürlich solltest du überall, wo du Dinge ersetzt hast und abgeschätzt hast, die notwendigen Informationen, wie du vorgegangen bist, dazu schreiben.

22.10.2008, 21:34

Svenja1986

Auf diesen Beitrag antworten »

Klar mache ich smile

smile

V I E L E N D A N K

22.10.2008, 23:07

Zizou66

Auf diesen Beitrag antworten »

Vielen Dank, dass ihr für mich übernommen habt. Ich musste leider kurzfristig weg, sonst hätte ich Bescheid gesagt Augenzwinkern

Augenzwinkern

23.10.2008, 00:05

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von WebFritzi

Zitat:

Original von tmo
Es reicht $\begin{eqnarray*} 3^n\cdot 3 \geq n^3+3n^2+3n+1 \end{eqnarray*}$ .

Nein, denn das ist nicht die Induktionsbehauptung.

Es sollte "Es reicht $\begin{eqnarray*} 3n^3 \geq n^3+3n^2+3n+1 \end{eqnarray*}$ ." lauten -,-

Jetzt kann ich ja auch noch mal meinen Weg erläutern.

Es ist $\begin{eqnarray*} \left(\frac{5}{4} \right)^3 = \frac{125}{64} < 3 \end{eqnarray*}$ , also

$\begin{eqnarray*} 3 > \left( 1+ \frac{1}{4} \right)^3 \end{eqnarray*}$ .

Wegen $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ ist $\begin{eqnarray*} 1+ \frac{1}{4} \geq 1+ \frac{1}{n} \end{eqnarray*}$

Also $\begin{eqnarray*} 3 > \left( 1+ \frac{1}{4} \right)^3 \geq \left( 1+ \frac{1}{n} \right)^3 \end{eqnarray*}$

Daraus folgt dann der entscheidende Schritt im Induktionschritt:
$\begin{eqnarray*} 3n^3 \geq \left( 1+ \frac{1}{n} \right)^3 \cdot n^3 = \left(n\left(1+\frac{1}{n}\right)\right)^3 = (n+1)^3 \end{eqnarray*}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »