Induktionsbeweis

16.10.2009, 13:27

Tawnos

Induktionsbeweis

Hallo

Ich habe mich die letzten Tage mit der vollständigen Induktion auseinandergesetzt.
Ich konnte sie auch einigermaßen nachvollziehen, wenn damit eine Relation "=" bewiesen werden soll.

Aber bei Ungleichungen habe ich da so meine Probleme mit dem Verständnis, ich habe mir deshalb auch mal den Workshop angeschaut und komme da beim 2ten Beispiel einfach nicht weiter.

Ich verstehe die Aufgabe bis hin zum Einsetzen der Vorraussetzung:

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

das das gleich ist der Aussage

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

kann ich auch nachvollziehen, aber ich frage mich warum man aus 2n und 1 das n rauszieht, welchen Sinn hat das?

Und ist es dann einfach offensichtlich, dass
$\begin{eqnarray*} n^{2} > n \cdot (2 + \frac{1}{n}) \end{eqnarray*}$ wahr ist, oder muss man da noch irgendwas zeigen?

Das andere 'einfache' Beispiel erschließt sich mir auch nicht.

Wenn ich $\begin{eqnarray*} \frac{n^{3}}{3} > 3 \cdot n - 3 \end{eqnarray*}$ habe, dann ist der Induktionsanfang ja:
$\begin{eqnarray*} n_{0} = 1 \end{eqnarray*}$

$\begin{eqnarray*} \frac{1^{3}}{3} = \frac{1}{3} \end{eqnarray*}$

und $\begin{eqnarray*} 3 \cdot 1 - 3 = 3 - 3 = 0 \end{eqnarray*}$

$\begin{eqnarray*} => \frac{1}{3} > 0 \end{eqnarray*}$

Dann kommt man also zum Induktionsschritt
$\begin{eqnarray*} n_{0} \end{eqnarray*}$ gilt für $\begin{eqnarray*} n >= 1 \end{eqnarray*}$

die Behauptung lautet, dass wenn n gilt auch n + 1 gilt.

Und das beweist man dann, und genau da fangen meine Probleme erst richtig an.

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

Ich beginne mit der linken Seite, habe aber leider keine Ahnung was ich tun könnte, weil ich meines Wissens nach keine Potenzgesetze anwenden kann:

$\begin{eqnarray*} \frac{(n + 1)^{3}}{3} = \frac{(n + 1) \cdot (n + 1)^{2}}{3} = (n + 1) \cdot \frac{(n + 1)^{2}}{3} \end{eqnarray*}$
aber das hilft mir meiner meinung nach nicht weiter, weil ich so nicht auf etwas komme was ich durch die Vorraussetzung ersetzen könnte.

Was mache ich also falsch, bzw was übersehe ich?

16.10.2009, 14:10

Schmonk

Auf diesen Beitrag antworten »

RE: Induktionsbeweis

Zitat:

Original von Tawnos
Hallo smile

Hallo!

Zitat:

Original von TawnosIch habe mich die letzten Tage mit der vollständigen Induktion auseinandergesetzt.
Ich konnte sie auch einigermaßen nachvollziehen, wenn damit eine Relation "=" bewiesen werden soll.

Aber bei Ungleichungen habe ich da so meine Probleme mit dem Verständnis, ich habe mir deshalb auch mal den Workshop angeschaut und komme da beim 2ten Beispiel einfach nicht weiter.

Die Betonung liegt hier wohl auf einigermaßen, denn sonst wäre dir auch das Vorgehen bei Ungleichungen klar. smile

Zitat:

Original von Tawnos
[...]aber ich frage mich warum man aus 2n und 1 das n rauszieht, welchen Sinn hat das?

Damit der Beweis elegant zu Ende geführt werden kann. Es gibt keinen zwingenden Grund jetzt n auszuklammern, du darfst das machen wie du willst, ich hätte es sicher auch anderes weitergerechnet.

Zitat:

Original von Tawnos
Und ist es dann einfach offensichtlich, dass
$\begin{eqnarray*} n^{2} > n \cdot (2 + \frac{1}{n}) \end{eqnarray*}$ wahr ist, oder muss man da noch irgendwas zeigen?

Ich finde, das ist nicht offensichtlich und man muss es ebenso per Induktion zeigen. Kann man aber sicherlich drüber diskutieren.

Zitat:

Original von Tawnos
Dann kommt man also zum Induktionsschritt
$\begin{eqnarray*} n_{0} \end{eqnarray*}$ gilt für $\begin{eqnarray*} n >= 1 \end{eqnarray*}$

die Behauptung lautet, dass wenn n gilt auch n + 1 gilt.

Deine leicht konfuse Formulierung weißt darauf hin, dass du eben nicht genau weißt, was du machen sollst.
Grundlage deines Induktionsbeweises sind die Peano-Axiome. Der Grundgedanke ist folgender: Wenn ich die Gültigkeit der zu zeigenden Aussage für $\begin{eqnarray*} n+1 \end{eqnarray*}$ aus der Gültigkeit der Aussage für $\begin{eqnarray*} n \end{eqnarray*}$ schließen kann, brauche ich die aussage nur noch für einen Startwert $\begin{eqnarray*} n_0 \end{eqnarray*}$ zeigen und habe sie damit für alle natürlichen Zahlen größer gleich $\begin{eqnarray*} n_0 \end{eqnarray*}$ bewiesen.
Ist dir dieser Grundgedanke soweit verständlich?
Es ist dabei vollkommen egal, ob du eine Gleichung oder eine Ungleichung beweisen willst.

Du willst also beweisen, dass

$\begin{eqnarray*} \frac{n^{3}}{3} > 3 \cdot n - 3 \end{eqnarray*}$

Dein Induktionsanfang stimmt.

Deine Induktionsvoraussetzung IV lautet nun:

$\begin{eqnarray*} \mbox{Es gelte } \frac{k^{3}}{3} > 3 \cdot k - 3 \mbox{ für ein } k\in\mathbb N \end{eqnarray*}$

Der eigentliche Induktionsschritt besteht nun darin, die zu beweisende Aussage für $\begin{eqnarray*} k+1 \end{eqnarray*}$ aus der IV zu folgern. Hilfreich könnte es sein, wenn du weißt, dass $\begin{eqnarray*} (k+1)^3=k^3+3k^2+3k+1 \end{eqnarray*}$ gilt. (siehe Pacalsches Dreieck)

Hilft dir das so erstmal weiter?

18.10.2009, 18:31

Tawnos

Auf diesen Beitrag antworten »

RE: Induktionsbeweis

Zitat:

Original von Schmonk

Zitat:

Die Betonung liegt hier wohl auf einigermaßen, denn sonst wäre dir auch das Vorgehen bei Ungleichungen klar. smile

Ja na die Sache die mich bei Ungleichungen einfach durcheinander bringt ist, dass ich etwas aus einer Relation einsetze und das dann auf einmal gleich etwas anderem sein soll.

Als Bsp einfach mal.

$\begin{eqnarray*} \sum_{k=1}^n 5^n > 5 \cdot n - 1 \sum_{k=1}^{n+1} 5^{n + 1} > 5 \cdot (n + 1) - 1 \sum_{k=1}^{n} 5^n + 5^{n + 1} = 5 \cdot n - 1 + 5^{n + 1} \end{eqnarray*}$

Da setzt man ja das kleinere, also das rechte, in den induktionsbeweis ein und auf einmal ist es gleich, genau das ist was ich an den ungleichungen halt noch komisch finde.

Zitat:

Original von Schmonk
Deine leicht konfuse Formulierung weißt darauf hin, dass du eben nicht genau weißt, was du machen sollst.
Grundlage deines Induktionsbeweises sind die Peano-Axiome. Der Grundgedanke ist folgender: Wenn ich die Gültigkeit der zu zeigenden Aussage für $\begin{eqnarray*} n+1 \end{eqnarray*}$ aus der Gültigkeit der Aussage für $\begin{eqnarray*} n \end{eqnarray*}$ schließen kann, brauche ich die aussage nur noch für einen Startwert $\begin{eqnarray*} n_0 \end{eqnarray*}$ zeigen und habe sie damit für alle natürlichen Zahlen größer gleich $\begin{eqnarray*} n_0 \end{eqnarray*}$ bewiesen.
Ist dir dieser Grundgedanke soweit verständlich?
[/qupte]

Ja das habe ich ja verstanden.

[quote]Original von Schmonk
Du willst also beweisen, dass

$\begin{eqnarray*} \frac{n^{3}}{3} > 3 \cdot n - 3 \end{eqnarray*}$

Dein Induktionsanfang stimmt.

Deine Induktionsvoraussetzung IV lautet nun:

$\begin{eqnarray*} \mbox{Es gelte } \frac{k^{3}}{3} > 3 \cdot k - 3 \mbox{ für ein } k\in\mathbb N \end{eqnarray*}$

Der eigentliche Induktionsschritt besteht nun darin, die zu beweisende Aussage für $\begin{eqnarray*} k+1 \end{eqnarray*}$ aus der IV zu folgern. Hilfreich könnte es sein, wenn du weißt, dass $\begin{eqnarray*} (k+1)^3=k^3+3k^2+3k+1 \end{eqnarray*}$ gilt. (siehe Pacalsches Dreieck)

Hilft dir das so erstmal weiter?

Hm, darüber hatte ich auch nachgedacht.
Aber da komme ich meiner Meinung nach auch nicht wirklich weiter.

Ich forme dann also um von:
$\begin{eqnarray*} \frac{k^3 + 3k^2 + 3k + 1}{3} = \frac{k^3}{3} + \frac{3k^2 + 3k + 1}{3} = 3k - 3 + \frac{3k^2 + 3k + 1}{3} \end{eqnarray*}$

Weiter umgeformt komme ich dann auf:

$\begin{eqnarray*} \frac{3k^2 + 12k - 8}{3} \end{eqnarray*}$

Und da sehe ich nun leider nicht wie ich auf $\begin{eqnarray*} 3 \cdot (k + 1) - 3 = 3k \end{eqnarray*}$ zurückkomme, ich sehe nichts zum ausklammern, umformen in bin- Formeln etc. ich hab bestimmt was falsch gemacht, weiss aber nicht was :/

Und dann habe ich noch mehr Aufgaben gefunden mit denen ich nicht klarkomme.
Zunächst erst einmal ein Problem mit der schreibweise.
Ich habe hier folgende Aufgabe:

$\begin{eqnarray*} a^{n + 1} - b^{n + 1} = (a - b) \sum_{k=0}^{n} a^{n-k} \cdot b^{k} \end{eqnarray*}$

Da weiss ich grundlegend einfach nicht wie ich mit n und k umgehen soll, ansich haben wir bisher immer für n k eingesetzt nd wenn nur k dastand war es halt auch normal k, bloß wenn ich nun für n k einsetze, dann reduziert sich das $\begin{eqnarray*} a^{n-k} \cdot b^{k} \end{eqnarray*}$ zu $\begin{eqnarray*} b^{k} \end{eqnarray*}$ und da bin ich mir nich sicher, ob das sinn und zweck der Sache ist.

Dann habe ich noch eine Aufgabe bei der mir einfach wieder der Ansatz fehlt:

$\begin{eqnarray*} \sum_{k=1}^{n} \frac{1}{\sqrt{k}} > \sqrt{n} \sum_{k=1}^{n+1} \frac{1}{\sqrt{k+1}} > \sqrt{n+1} \sum_{k=1}^n \frac{1}{\sqrt{k}} + \frac{1}{\sqrt{k+1}} = \sqrt{k} + \frac{1}{\sqrt{k+1}} \end{eqnarray*}$

Und da verzweifel ich dann auch schon wieder :/

Und als allerletztes Problem habe ich dann noch folgende Aufgabenstellung, und zwar sollte

$\begin{eqnarray*} \sum_{k=0}^{n} x^{k} = \frac{1 - x^{n+1}}{1 - x} \end{eqnarray*}$ für x ungleich 1

induktiv bewiesen werden, das habe ich auch lösen können.
Nun soll ich genau das gleiche aber auch noch direkt beweisen.
Mich verwirrt aber die Summenschreibweise zu sehr als dass ich wüsste wie ich die linke in die rechte Seite per Umformung überführen könnte.

Wieder einmal fragen über fragen, schlimm, ich weiss :/

18.10.2009, 19:55

Schmonk

Auf diesen Beitrag antworten »

RE: Induktionsbeweis

Zitat:

Original von Tawnos
Ja na die Sache die mich bei Ungleichungen einfach durcheinander bringt ist, dass ich etwas aus einer Relation einsetze und das dann auf einmal gleich etwas anderem sein soll.
Als Bsp einfach mal.

$\begin{eqnarray*} \sum_{k=1}^n 5^n > 5 \cdot n - 1 \sum_{k=1}^{n+1} 5^{n + 1} > 5 \cdot (n + 1) - 1 \sum_{k=1}^{n} 5^n + 5^{n + 1} = 5 \cdot n - 1 + 5^{n + 1} \end{eqnarray*}$

Da setzt man ja das kleinere, also das rechte, in den induktionsbeweis ein und auf einmal ist es gleich, genau das ist was ich an den ungleichungen halt noch komisch finde.

Das von dir beschriebene fände ich auch komisch, aber sowas macht man ja auch nicht. Ich greife einfach mal dein Beispiel auf. Zuerst einmal ist da wohl etwas mit den n und k durcheinander geraten, aber ich denke, ich verstehe, wo dein Problem liegt.

Also zu beweisen ist
$\begin{eqnarray*} \sum_{k=1}^n 5^k > 5 \cdot n - 1 \end{eqnarray*}$
Der Induktionsanfang (n=1) ist leicht und dürfte keine Probleme machen.
Es gelte nun also die obige Aussage für ein festes n, um die Aussage per Induktion zu beweisen, muss ich also
$\begin{eqnarray*} \sum_{k=1}^{n+1} 5^{k} > 5 \cdot (n + 1) - 1 \end{eqnarray*}$
aus der geltenden Aussage für n folgern:

$\begin{eqnarray*} \sum_{k=1}^{n+1} 5^k = \sum_{k=1}^n 5^k + 5^{n+1} > 5 \cdot n - 1 +5^{n+1} \geq 5 \cdot n - 1 +5 =5 \cdot (n + 1) - 1 \end{eqnarray*}$
Also
$\begin{eqnarray*} \sum_{k=1}^{n+1} 5^{k} > 5 \cdot (n + 1) - 1 \end{eqnarray*}$

Dass die erste Gleichheit gilt, ist klar, diese Umformung nimmt man vor, damit man sich auf die schon bekannte Abschätzung für n beziehen kann, also die Induktionsvoraussetzung.
Die erste Abschätzung darf man wegen der Induktionsvoraussetzung durchführen. Ich empfehle dir, gerade am Anfang das verwenden der Induktionsvoraussetzung durch ein kleines IV auf dem Relationszeichen zu verdeutlichen.
Die nächste Abschätzung nutzt einfach die Tatsache, dass $\begin{eqnarray*} 5^{n+1}\geq 5 \end{eqnarray*}$ ist. Das glaubt man sicherlich auch ohne Induktionsbeweis.
Im letzten Schritt habe ich nur noch ein bischen umgeordnet und ausgeklammert.

Du siehst, es wurde nirgendwo irgendetwas Kleineres plötzlich mit irgendetwas Anderem gleichgesetzt, sondern jeder Schritt ist erklärbar. Kannst du alles nachvollziehen?

Nun also zum Beweis von
$\begin{eqnarray*} \frac{n^{3}}{3} > 3 \cdot n - 3 \end{eqnarray*}$
Du hast recht, dieser Beweis ist etwas tricky, ich werde ihn dir aufschreiben, dann siehst du, dass du nichts falsch gemacht hast, aber dir eine wichtige Idee fehlte, nämlich eine mutige Abschätzung, welche du ebenso per Induktion beweisen musst.
Damit wird idR jeder Student geärgert und die damit verbundene Einsicht führt dann zum erwünschten Aha-Effekt.
Wie du richtig bemerkt hast, ist das Ziel deines Induktionsschrittes:
$\begin{eqnarray*} \frac{(k+1)^3}3>3n \end{eqnarray*}$
Die Abschätzung dazu geht wie folgt:

$\begin{eqnarray*} \frac{(k+1)^3}3=\frac{k^3+3k^2+3k+1}3=\frac{k^3}3+k^2+k+\frac 13\geq \frac{k^3}3+3>3n-3+3=3n \end{eqnarray*}$

Die letzte Abschätzung folgt aus der Induktionsvoraussetzung, die Abschätzung davor, nämlich $\begin{eqnarray*} k^2+k+\frac 13 \geq 3 \end{eqnarray*}$ vereinfacht dir das Leben unheimlich, muss aber ebenso (z.B. per Induktion) bewiesen werden. Genaugenommen kann man auch argumentieren, dass ja schon $\begin{eqnarray*} k^2>3 \end{eqnarray*}$ für $\begin{eqnarray*} k>2 \end{eqnarray*}$ gilt. Aus Übungsgründen empfehle ich dir, die Aussage aber auch per Induktion zu beweisen.
Es gibt ähnliche Beweise, wo du auch mutig Abschätzen musst und dann dies Abschätzung ggf. ebenso per Induktion beweisen musst.

Zitat:

Original von Tawnos
Und dann habe ich noch mehr Aufgaben gefunden mit denen ich nicht klarkomme.
Zunächst erst einmal ein Problem mit der schreibweise.
Ich habe hier folgende Aufgabe:

$\begin{eqnarray*} a^{n + 1} - b^{n + 1} = (a - b) \sum_{k=0}^{n} a^{n-k} \cdot b^{k} \end{eqnarray*}$

Da weiss ich grundlegend einfach nicht wie ich mit n und k umgehen soll, ansich haben wir bisher immer für n k eingesetzt nd wenn nur k dastand war es halt auch normal k, bloß wenn ich nun für n k einsetze, dann reduziert sich das $\begin{eqnarray*} a^{n-k} \cdot b^{k} \end{eqnarray*}$ zu $\begin{eqnarray*} b^{k} \end{eqnarray*}$ und da bin ich mir nich sicher, ob das sinn und zweck der Sache ist.

Wieso kommst du auf die Idee, n in k einzusetzen? Da du schon oben und imfolgenden auch durcheinanderkommst, nochmal ganz generell: in diesem Fall erfolgt die Induktion über n, k bleibt demnach komplett unberührt. k ist nur der Zählindex.
Schreibe dir immer ganz klar und sauber auf, was du zeigen willst, dann kommst du auch nicht durcheinander. Wenn du einen Induktionsbeweis führst und dabei Reihen verwendest, dann schau genau hin, was du beweisen willst, welche Zahl die Induktionsvariable ist und welche nicht. Induktion wird immer nur über eine Zahl geführt. Ich bin mir sicher, dass du obiges Problem allein beweisen kannst, ich verdeutliche mein Anliegen einfach an deinem nächsten Beispiel:
$\begin{eqnarray*} \sum_{k=1}^{n} \frac{1}{\sqrt{k}} > \sqrt{n} \end{eqnarray*}$
Du glaubst jetzt, dass dein Induktionsschritt so auszusehen hat:
$\begin{eqnarray*} \sum_{k=1}^{n+1} \frac{1}{\sqrt{k+1}} > \sqrt{n+1} \end{eqnarray*}$
DAS IST FALSCH!

Ich gebe dir jetzt gern noch ein Muster, nach dieser Art solltest du einen Induktionsbeweis formal immer aufbauen, dann sollten solche Fehler nicht passieren.

ZU BEWEISEN:
$\begin{eqnarray*} \sum_{k=1}^{n} \frac{1}{\sqrt{k}} > \sqrt{n} \end{eqnarray*}$
BEWEIS:
Beweis mit Induktion über n
Induktionsanfang (IA): n=1
$\begin{eqnarray*} \sum_{k=1}^{1} \frac{1}{\sqrt{k}}=\frac{1}{\sqrt{1}}=1 \geq \sqrt{1}~~~~\mbox{wahre Aussage} \end{eqnarray*}$
Induktionsvoraussetzung (IV):
Es gelte
$\begin{eqnarray*} \sum_{k=1}^{n} \frac{1}{\sqrt{k}} > \sqrt{n} \end{eqnarray*}$
für ein festes $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ .
Induktionsschritt (IS): Beweisen der Aussage für n+1
Es ist also zu zeigen:
$\begin{eqnarray*} \sum_{k=1}^{n+1} \frac{1}{\sqrt{k}} > \sqrt{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=1}^{n+1} \frac{1}{\sqrt{k}} = \sum_{k=1}^{n} \frac{1}{\sqrt{k}} + \frac 1{\sqrt{n+1}} \geq \sqrt{n}+\frac 1{\sqrt{n+1}}\geq \sqrt{n+1} \end{eqnarray*}$

Die letzte Abschätzung bedarf sicherlich noch einer Erläuterung, wie gesagt, das mutige und gezielte Abschätzen wird sich noch entwickeln:
Es ist
$\begin{eqnarray*} n+1=\sqrt{(n+1)^2}=\sqrt{n^2+2n+1}\geq\sqrt{n^2+n}\geq\sqrt{n^2}=n \end{eqnarray*}$
Es gilt also
$\begin{eqnarray*} \sqrt{n^2+n}\geq n \end{eqnarray*}$
bzw.
$\begin{eqnarray*} \sqrt{n(n+1)}+1\geq n+1 \end{eqnarray*}$
also
$\begin{eqnarray*} \sqrt{n}\sqrt{n+1}+1\geq n+1 \end{eqnarray*}$
Division durch $\begin{eqnarray*} \sqrt{n+1} \end{eqnarray*}$ liefert die gewünschte Abschätzung.
QED

Zitat:

Original von Tawnos
Und als allerletztes Problem habe ich dann noch folgende Aufgabenstellung, und zwar sollte

$\begin{eqnarray*} \sum_{k=0}^{n} x^{k} = \frac{1 - x^{n+1}}{1 - x} \end{eqnarray*}$ für x ungleich 1

induktiv bewiesen werden, das habe ich auch lösen können.
Nun soll ich genau das gleiche aber auch noch direkt beweisen.

Aber auch wirklich die allerletzte Frage. böse

Erst einmal Gratulation, dass du den Induktionsbeweis geschafft hast. Das bestärkt mich in der annahme, dass dein eigentliches Problem nicht der Induktionsbeweis, sondern das Abschätzen ist.

Ich gebe dir einfach mal folgenden Tipp für den direkten Beweis:

$\begin{eqnarray*} s_n:=\sum_{k=0}^{n} x^{k}=1+x+x^2+\ldots+x^n \end{eqnarray*}$

Wie sieht also $\begin{eqnarray*} x\cdot s_n \end{eqnarray*}$ aus?
Bilde nun die Differenz $\begin{eqnarray*} s_n-x\cdot s_n \end{eqnarray*}$ und die Lösung sollte dich anspringen, wenn du dann nach $\begin{eqnarray*} s_n \end{eqnarray*}$ umstellst. Augenzwinkern

Grüße!

18.10.2009, 20:33

Tawnos

Auf diesen Beitrag antworten »

RE: Induktionsbeweis

Zitat:

Original von Schmonk
Also zu beweisen ist
$\begin{eqnarray*} \sum_{k=1}^n 5^k > 5 \cdot n - 1 \end{eqnarray*}$
Der Induktionsanfang (n=1) ist leicht und dürfte keine Probleme machen.
Es gelte nun also die obige Aussage für ein festes n, um die Aussage per Induktion zu beweisen, muss ich also
$\begin{eqnarray*} \sum_{k=1}^{n+1} 5^{k} > 5 \cdot (n + 1) - 1 \end{eqnarray*}$
aus der geltenden Aussage für n folgern:

$\begin{eqnarray*} \sum_{k=1}^{n+1} 5^k = \sum_{k=1}^n 5^k + 5^{n+1} > 5 \cdot n - 1 +5^{n+1} \geq 5 \cdot n - 1 +5 =5 \cdot (n + 1) - 1 \end{eqnarray*}$
Also
$\begin{eqnarray*} \sum_{k=1}^{n+1} 5^{k} > 5 \cdot (n + 1) - 1 \end{eqnarray*}$

Dass die erste Gleichheit gilt, ist klar, diese Umformung nimmt man vor, damit man sich auf die schon bekannte Abschätzung für n beziehen kann, also die Induktionsvoraussetzung.
Die erste Abschätzung darf man wegen der Induktionsvoraussetzung durchführen. Ich empfehle dir, gerade am Anfang das verwenden der Induktionsvoraussetzung durch ein kleines IV auf dem Relationszeichen zu verdeutlichen.
Die nächste Abschätzung nutzt einfach die Tatsache, dass $\begin{eqnarray*} 5^{n+1}\geq 5 \end{eqnarray*}$ ist. Das glaubt man sicherlich auch ohne Induktionsbeweis.
Im letzten Schritt habe ich nur noch ein bischen umgeordnet und ausgeklammert.

Du siehst, es wurde nirgendwo irgendetwas Kleineres plötzlich mit irgendetwas Anderem gleichgesetzt, sondern jeder Schritt ist erklärbar. Kannst du alles nachvollziehen?

Okay, ausgenommen von dem, warum ich was machen darf in Sachen Vorraussetzung ist es verstanden.
Ich weiss wo mein Denkfehler lag, ich hab nicht mehr daran gedacht, dass der Prof immer Implikationspfeile genommen hat, dann ergibt das natürlich auch Sinn.
Mensch an was für Banalitäten man doch scheitern kann geschockt

Zitat:

Original von Schmonk
Nun also zum Beweis von
$\begin{eqnarray*} \frac{n^{3}}{3} > 3 \cdot n - 3 \end{eqnarray*}$
Du hast recht, dieser Beweis ist etwas tricky, ich werde ihn dir aufschreiben, dann siehst du, dass du nichts falsch gemacht hast, aber dir eine wichtige Idee fehlte, nämlich eine mutige Abschätzung, welche du ebenso per Induktion beweisen musst.
Damit wird idR jeder Student geärgert und die damit verbundene Einsicht führt dann zum erwünschten Aha-Effekt.
Wie du richtig bemerkt hast, ist das Ziel deines Induktionsschrittes:
$\begin{eqnarray*} \frac{(k+1)^3}3>3n \end{eqnarray*}$
Die Abschätzung dazu geht wie folgt:

$\begin{eqnarray*} \frac{(k+1)^3}3=\frac{k^3+3k^2+3k+1}3=\frac{k^3}3+k^2+k+\frac 13\geq \frac{k^3}3+3>3n-3+3=3n \end{eqnarray*}$

Die letzte Abschätzung folgt aus der Induktionsvoraussetzung, die Abschätzung davor, nämlich $\begin{eqnarray*} k^2+k+\frac 13 \geq 3 \end{eqnarray*}$ vereinfacht dir das Leben unheimlich, muss aber ebenso (z.B. per Induktion) bewiesen werden. Genaugenommen kann man auch argumentieren, dass ja schon $\begin{eqnarray*} k^2>3 \end{eqnarray*}$ für $\begin{eqnarray*} k>2 \end{eqnarray*}$ gilt. Aus Übungsgründen empfehle ich dir, die Aussage aber auch per Induktion zu beweisen.
Es gibt ähnliche Beweise, wo du auch mutig Abschätzen musst und dann dies Abschätzung ggf. ebenso per Induktion beweisen musst.

Ja, jetzt seh ichs, aber solch Abschätzung ist schon ganz schön happig :/
Aber wenn ich die Abschätzung so mache und die bewiesen habe kann ich mit dem Ausgangsbeispiel weitermachen oder war das jetzt schon bewiesen? Ich denke nicht, sah für mich nicht so aus.

Zitat:

Original von Schmonk

Zitat:

JAAAAAAAAA Big Laugh

Na klar, man, als ob man die ganze zeit Tomaten auf den Augen gehabt hätte.
Das der Aha-Effekt immer so spät kommen muss traurig

Zitat:

Original von Schmonk

Zitat:

Aber auch wirklich die allerletzte Frage. böse

Grüße!

Ich muss zu meiner Schande gestehen, dass ich absolut keine Ahnung habe was $\begin{eqnarray*} s_n:= \end{eqnarray*}$ bedeuten soll bzw was $\begin{eqnarray*} x \cdot s_n \end{eqnarray*}$ sein soll Oo
Habe ich jetzt noch garnicht kennengelernt während der Vorlesungen.

Aber bis hierhin schonmal vielen vielen lieben Dank, du hast mir seeehr geholfen!

Gott

19.10.2009, 00:19

Tawnos

Auf diesen Beitrag antworten »

RE: Induktionsbeweis

Zitat:

So, ich möchte gerne nochmal das aufgreifen, vllt kann mir da ja jemand relativ zeitnah helfen.

Ich hab das grundlegende verstanden und stecke nun im IB fest.
Was ich bisher gemacht habe:

IS: $\begin{eqnarray*} a^{n+2} - b^{n+2} = (a-b) \sum_{k=0}^{n+1} a^{n-k+1}b^{k} \end{eqnarray*}$

IB: $\begin{eqnarray*} (a-b) \cdot \sum_{k=0}^{n} a^{n-k]}b^{k} + (a-b) \cdot a^{n-k+1}b^{k} = a^{n+1} - b^{n+1} + (a-b) \cdot a^{n-k+1}b^{k} = a \cdot a^n - b \cdot b^n + a^2 \cdot a^n \cdot a^{-k} \cdot b^k - a \cdot a^n \cdot a^{-k} \cdot b \cdot b^k \end{eqnarray*}$

Mein problem ist jetzt einfach, dass ich nicht weiss was ich mit dem k anfangen kann, das blockiert mir ja völlig die möglichkeit vernünftig zu verinfachen oder sehe ich das was falsch?
Wie gehe ich am besten weiter vor?

Wäre toll wenn sich da zu später Stunde noch jemand findet der mir einen kurzen Denkanstoß geben kann smile

19.10.2009, 09:00

klarsoweit

Auf diesen Beitrag antworten »

RE: Induktionsbeweis
Da geht aber einiges durcheinander. unglücklich

Zunächst mal ist $\begin{eqnarray*} (a-b) \sum_{k=0}^{n+1} a^{n-k+1}b^{k} \end{eqnarray*}$ nicht dasselbe wie $\begin{eqnarray*} (a-b) \cdot \sum_{k=0}^{n} a^{n-k+1}b^{k} + (a-b) \cdot a^{n-k+1}b^{k} \end{eqnarray*}$ , falls dieses komische "]" für "+1" stehen sollte. Am besten formulierst du nochmal genau, was du uns sagen willst.

19.10.2009, 10:36

Schmonk

Auf diesen Beitrag antworten »

RE: Induktionsbeweis

Zitat:

Original von Tawnos
Was ich bisher gemacht habe:

IS: $\begin{eqnarray*} a^{n+2} - b^{n+2} = (a-b) \sum_{k=0}^{n+1} a^{n-k+1}b^{k} \end{eqnarray*}$

IB: $\begin{eqnarray*} (a-b) \cdot \sum_{k=0}^{n} a^{n-k]}b^{k} + (a-b) \cdot a^{n-k+1}b^{k} = a^{n+1} - b^{n+1} + (a-b) \cdot a^{n-k+1}b^{k} = a \cdot a^n - b \cdot b^n + a^2 \cdot a^n \cdot a^{-k} \cdot b^k - a \cdot a^n \cdot a^{-k} \cdot b \cdot b^k \end{eqnarray*}$

Du hast richtig festgestellt, dass du im Induktionsschritt
$\begin{eqnarray*} a^{n+2} - b^{n+2} = (a-b) \sum_{k=0}^{n+1} a^{n-k+1}b^{k} \end{eqnarray*}$
zeigen musst.
Es ist auch gut, dass du erkannt hast, dass der Beweis der Gleichung leichter von der rechten Seite aus zu führen ist.
Was du dann aber machst, ist ziemlicher Unsinn. Sauberes Aufschreiben sollte dir weiterhelfen, dass du nicht immer n und k verwechselst.

$\begin{eqnarray*} (a-b) \sum_{k=0}^{n+1} a^{n-k+1}b^{k}=(a-b)\left(\sum_{k=0}^{n} a^{n-k+1}b^{k}+a^{0}b^{n+1}\right)=(a-b)\left(a\sum_{k=0}^{n}a^{n-k}b^{k}+b^{n+1}\right)=a\cdot(a-b)\sum_{k=0}^{n} a^{n-k}b^{k}+(a-b)b^{n+1} \end{eqnarray*}$

Jetzt kannst du endlich die Induktionsvoraussetzung anwenden. Also von nun an bitte volle Konzentration, damit du nicht mehr solche Faselfehler machst.

Zitat:

Original von Tawnos
Ich muss zu meiner Schande gestehen, dass ich absolut keine Ahnung habe was $\begin{eqnarray*} s_n:= \end{eqnarray*}$ bedeuten soll bzw was $\begin{eqnarray*} x \cdot s_n \end{eqnarray*}$ sein soll Oo
Habe ich jetzt noch garnicht kennengelernt während der Vorlesungen.

Ihr hattet in der Vorlesung noch nicht das definierende Gleichheitszeichen?

Zitat:

Die Abwandlungen »:=« bzw. »=:« werden in der Mathematik benutzt, um eine Definition einer Seite durch die andere Seite darzustellen. Dabei stehen die Doppelpunkte immer bei dem zu definierenden Objekt.

Ich habe also nichts anderes gemacht, als der von dir angegebenen Reihe einen Variablennamen zuzuweisen, einfach zum kürzeren Aufschreiben. $\begin{eqnarray*} s_n \end{eqnarray*}$ bezeichnet also immer noch deine Summe, man sagt hierzu auch Partialsumme, falls du noch ein bischen den Herrn Google befragen willst.

$\begin{eqnarray*} x \cdot s_n=x\cdot\sum_{k=0}^{n} x^{k} \end{eqnarray*}$ bezeichnet also demnach eine ganz schnöde Multiplikation, ich unterstelle einfach mal, dass du damit umgehen kannst. Augenzwinkern

Gruß

Neue Frage »

Antworten »

Induktionsbeweis

Verwandte Themen