Vollständige Induktion - Wie geht das?

20.06.2011, 22:39

Fish-Guts

Auf diesen Beitrag antworten »

Vollständige Induktion - Wie geht das?

Ich bin grade an einer Aufgabe dran, in der folgendes gefragt wird:

Beweisen Sie mit Induktion für alle $\begin{eqnarray*} n \in \mathbb N: \end{eqnarray*}$

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^n k^{2} = n (n + 1)(2n + 1) \end{eqnarray*}$

Nun weiss ich aus der Vorlesung, dass dies in zwei Schritten geschieht:

1. Die Induktionsverankerung, die ist in diesem Falle

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^1 k^{2} = 1 (1 + 1)(2*1 + 1) \end{eqnarray*}$

Korrekt?

2. Der Induktionsschritt. Wie kann ich hier irgendwelche Bildungsregeln lernen? Ich habe hier leider keine Idee, wann ich hier (n+1) für den Induktionssschritt einbauen soll.

Danke für eure Hilfe.

20.06.2011, 22:40

tigerbine

Auf diesen Beitrag antworten »

So geht das: [WS] Vollständige Induktion

20.06.2011, 23:00

Fish-Guts

Auf diesen Beitrag antworten »

Danke. Das hat geholfen. Ich habe folgende Lösung:

1. Induktionsverankerung:

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^1 k^{2} = 1 (1 + 1)(2*1 + 1) \end{eqnarray*}$

2. Induktionsschritt

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^(n+1) k^{2} = n (n + 1 + 1)(2n + 3) \end{eqnarray*}$

Reicht jetzt das als Lösung? Oder muss ich noch Zahlen einsetzen? Im Script steht immer was von i.A. über dem Gleichheitszeichen (in Annahme), verstehe aber nicht genau was er damit meint. Danke.

20.06.2011, 23:24

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Im Script steht immer was von i.A. über dem Gleichheitszeichen (in Annahme), verstehe aber nicht genau was er damit meint.

Dann hast du das Prinzip auch noch nicht verstanden. Also den WS noch mal lesen.

20.06.2011, 23:47

Fish-Guts

Auf diesen Beitrag antworten »

Hmm

Also wenn ich mein Hirn nun trauen darf, habe ich die Induktion korrekt angewandt. Und im WS sehe ich keine i.A. über irgendwelchen Gleichheitszeichen...

20.06.2011, 23:51

tigerbine

Auf diesen Beitrag antworten »

Du hast doch erst den Anfang der Induktion hingeschrieben und das was im Zitat steht ist essentiel für das Verständnis. Von der lösung bist du noch weit weg.

Anzeige

21.06.2011, 00:03

Fish-Guts

Auf diesen Beitrag antworten »

Also jetzt bin ich verwirrt.

Ich habe das Beispiel 1 im WS zur Hilfe genommen als Basis für meine Aufgabe.

Meine Aufgabe:

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^n k^{2} = n (n + 1)(2n + 1) \end{eqnarray*}$

Meine Induktionsverankerung (oder Induktionsanfang in eurer Notation)

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^1 k^{2} = 1 (1 + 1)(2*1 + 1) \end{eqnarray*}$

Dann führe ich den Induktionschritt mit $\begin{eqnarray*} n+1 \end{eqnarray*}$ durch:

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^{n+1} k^{2} = n (n + 1 + 1)(2n + 3) \end{eqnarray*}$

Was ist jetzt daran falsch?

21.06.2011, 00:15

tigerbine

Auf diesen Beitrag antworten »

Falsch ist, dass du nur zeigst, für einen Startwert gilt es und dann die Formel einfach benutzt um den Term für n+1 hinuzuschreiben. wo bleibt:

Zitat:

Original von Deakandy
1. Beispiel
Für alle $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gilt: $\begin{eqnarray*} \sum_{k=1}^n~k = 1+2+...+n = \frac{n\cdot(n+1)}{2} \end{eqnarray*}$

Beweis: Wir zeigen die Aussage durch Induktion nach n
Induktionsanfang (IA): Man zeige, dass n=1 gilt
$\begin{eqnarray*} \sum_{k=1}^1~k = 1 = \frac{1\cdot(1+1)}{2} \end{eqnarray*}$

Induktionsvorraussetzung (IV): Es gelte für ein $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$

Induktionsschluss (IS): Man schließe von n auf n+1: $\begin{eqnarray*} n \rightarrow n+1 \end{eqnarray*}$
Das heißt man hat zu zeigen, das folgendes gilt:
$\begin{eqnarray*} \sum_{k=1}^{n+1}~k = \frac{(n+1) \cdot(n+1+1)}{2} = \frac{(n+1) \cdot (n+2)}{2} = \frac {n^2+3n+2}{2} \end{eqnarray*}$
Nun geht man wie folgt vor:
$\begin{eqnarray*} \sum_{k=1}^{n+1}~k = (\sum_{k=1}^n~k) +(n+1) \end{eqnarray*}$
In diesem Schritt holt man lediglich den letzten Summanden raus.
Nun kann man die Induktionsvorraussetzung anwenden
Man setzt für die Summe
$\begin{eqnarray*} \sum_{k=1}^n~k \end{eqnarray*}$ genau das ein, was aus der Voraussetzung gilt und zwar $\begin{eqnarray*} \frac{n\cdot(n+1)}{2} \end{eqnarray*}$
Eingesetzt ergibt sich dann folgender Term:

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

Diese Summe bringt man geschickt auf einen Bruch durch Erweitern

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

$\begin{eqnarray*} \frac {(n^2+n)+(2n+2)} {2} \end{eqnarray*}$

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

Und genau das war zu zeigen.
Man hat nun genau die Form, wie sie unter dem Induktionsschluss stehen hat.
Die Behauptung ist dem Prinzip der vollständigen Induktion bewiesen. q.e.d.

21.06.2011, 01:41

Fish-Guts

Auf diesen Beitrag antworten »

Wenn ich das nun richtig verstehe mache ich also folgendes:

1. Induktionsverankerung

$\begin{eqnarray*} 6* \sum\limits_{k=1}^n k^2 = 1(1+1)(2*1+1) \end{eqnarray*}$

Es gilt zu zeigen, dass

$\begin{eqnarray*} 6 * \sum\limits_{k=1}^{n+1} k^{2} = n (n + 1 + 1)(2n + 3) \end{eqnarray*}$

2. Induktionsschluss: Man schließe von n auf n+1: $\begin{eqnarray*} n \rightarrow n+1 \end{eqnarray*}$

Dann habe ich folgendes:

$\begin{eqnarray*} 6* \sum\limits_{k=1}^{n+1} k^2 = 6 * \sum\limits_{k=1}^{n} k^2 +(n+1) \end{eqnarray*}$

also setze ich für $\begin{eqnarray*} 6 * \sum\limits_{k=1}^{n} k^2 \end{eqnarray*}$ folgendes ein:

$\begin{eqnarray*} n (n + 1)(2n + 1) \end{eqnarray*}$ und daraus folgt: $\begin{eqnarray*} n (n + 1)(2n + 1)+n+1 \end{eqnarray*}$ , was ergibt:

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

Das scheint aber nicht zu stimmen. Wo mache in den Fehler?

21.06.2011, 01:49

tigerbine

Auf diesen Beitrag antworten »

Schon der Beginn ist falsch. Dort muss ja n=1 gelten. [du hast da n in der Summe stehen]. Und von der Scheibweise her auch nicht richtig.

$\begin{eqnarray*} 6 =6 \cdot 1= 6\cdot \sum\limits_{k=1}^1 k^2 = 1(1+1)(2\cdot 1+1) = 2\cdot 3 =6 \end{eqnarray*}$

Somit stimmt die Formel für n=1. Sei sie richtig für n, dann gilt

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^n k^{2} = n (n + 1)(2n + 1) \end{eqnarray*}$

Frage: Gilt die Formel auch für n+1?

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2<br /> &&= n (n + 1)(2n + 1) + 6 \cdot (n+1)^2<br /> && =...<br /> && \stackrel {?} =(n+1)((n+1)+1)(2(n+1) + 1) \end{eqnarray*}$

21.06.2011, 01:50

tigerbine

Auf diesen Beitrag antworten »

Schon der Beginn ist falsch. Dort muss ja n=1 gelten. [du hast da n in der Summe stehen]. Und von der Scheibweise her auch nicht richtig.

$\begin{eqnarray*} 6 =6 \cdot 1= 6\cdot \sum\limits_{k=1}^1 k^2 = 1(1+1)(2\cdot 1+1) = 2\cdot 3 =6 \end{eqnarray*}$

Somit stimmt die Formel für n=1. Sei sie richtig für n, dann gilt

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^n k^{2} = n (n + 1)(2n + 1) \end{eqnarray*}$

Frage: Gilt die Formel auch für n+1?

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2<br /> &&= n (n + 1)(2n + 1) + 6 \cdot (n+1)^2<br /> && =...<br /> && \stackrel {?} =(n+1)((n+1)+1)(2(n+1) + 1) \end{eqnarray*}$

Zitat:

$\begin{eqnarray*} 6* \sum\limits_{k=1}^{n+1} k^2 = 6 * \sum\limits_{k=1}^{n} k^2 +(n+1) \end{eqnarray*}$

Quadrat fehlt.

21.06.2011, 02:04

Fish-Guts

Auf diesen Beitrag antworten »

Beginn ist klar, hab eben copy/paste gemacht, in meinen handschriftlichen Notitzen hab ichs mit n = 1.

Zum Verständnis:

Setze ich hier
$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2 \end{eqnarray*}$

das so ein, dass n+1 anstelle von $\begin{eqnarray*} \sum\limits_{k=1}^{n} k \end{eqnarray*}$ steht?

Geht mir darum zu verstehen, wie ich n+1 einsetzen muss. Aber so wie du das geschrieben hast, leuchtet es mir glaube ich ein...

21.06.2011, 02:09

tigerbine

Auf diesen Beitrag antworten »

Ich habe lediglich auf beiden Seiten der Formel statt n eben (n+1) eingesetzt. Das muss man halt auch korrekt machen, Klammern helfen.

21.06.2011, 21:02

Fish-Guts

Auf diesen Beitrag antworten »

Ist es so nun korrekt?

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n} k^2 = n(n+1)(2n+1) \end{eqnarray*}$

1. Induktionsverankerung mit n = 1

$\begin{eqnarray*} 6 =6 \cdot 1= 6\cdot \sum\limits_{k=1}^1 k^2 = 1(1+1)(2\cdot 1+1) = 2\cdot 3 =6 \end{eqnarray*}$

2. Induktionsschritt

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^n k^{2} = n (n + 1)(2n + 1) \end{eqnarray*}$ gilt somit für n = 1;

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} = (n +1)(n + 1 + 1)(2n + 3) \end{eqnarray*}$ (zu zeigen)

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2 <br /><br /> &&= 2n^3 + 9n^2 + 13n + 6<br /><br /> &&= (n+1)(n+2)(2n+3)<br /><br /> <br /> \end{eqnarray*}$

Mit $\begin{eqnarray*} n = 4<br /> <br /> 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} = (n +1)(n + 1 + 1)(2n + 3) \end{eqnarray*}$
$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{5} k^{2} = (5)(6)(11)<br /> <br /> = 6 \cdot 55 = (5)(6)(11)<br /> => 330 = 330<br /> <br /> \end{eqnarray*}$

Ist das nun so korrekt bewiesen, oder fehlt da noch was?

21.06.2011, 21:14

tigerbine

Auf diesen Beitrag antworten »

Du hast den formalen Aufbau immer noch nicht verstanden. Ich hatte ihn doch schon vorgemacht. Es war nur noch eine Rechnung auszuführen. Induktion besteht aus 3 Schritten.

Zitat:

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2<br /> &&= 6 \cdot n (n + 1)(2n + 1) + 6 \cdot (n+1)^2<br /> && =...<br /> && \stackrel {?} =(n+1)((n+1)+1)(2(n+1) + 1) \end{eqnarray*}$

Was soll das "n=4" mittendrin? verwirrt

verwirrt

21.06.2011, 21:31

Fish-Guts

Auf diesen Beitrag antworten »

Ach das n=4 hat in die mitte gerutscht. Damit wollte ich noch format beweisen, dass die Rechnung stimmt.

Abgsehen davon sind die letzten drei Zeilen meiner Rechnung so berechnet.

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2 <br /><br /> &&= 2n^3 + 9n^2 + 13n + 6<br /><br /> &&= (n+1)(n+2)(2n+3)<br /><br /> <br /> \end{eqnarray*}$

Ich kann den einen Zwischenschritt natürlich noch mitreinnehmen:

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2<br /> <br />&&= n(n+1)(2n+1) + 6 (n+1)^2<br /> <br />&&= 2n^3 + 9n^2 + 13n + 6<br /><br /> &&= (n+1)(n+2)(2n+3) \end{eqnarray*}$

Ausserdem stimmt deine Ausgangsrechnung nicht:

Zitat:

$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n+1} k^{2} &&= 6 \cdot \sum\limits_{k=1}^{n} k^{2} + 6 \cdot (n+1)^2<br /> &&= 6 \cdot n (n + 1)(2n + 1) + 6 \cdot (n+1)^2<br /> && =...<br /> && \stackrel {?} =(n+1)((n+1)+1)(2(n+1) + 1) \end{eqnarray*}$

Zweite Zeile ist falsch, da
$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n} k^2 = n(n+1)(2n+1) \end{eqnarray*}$ und nicht
$\begin{eqnarray*} 6 \cdot \sum\limits_{k=1}^{n} k^2 = 6 \cdot n(n+1)(2n+1) \end{eqnarray*}$ ist.

21.06.2011, 22:33

tigerbine

Auf diesen Beitrag antworten »

Die 6, die zu biel habe, habe ich entfernt.

Dann haben wir es jetzt ja.

22.06.2011, 00:55

Fish-Guts

Auf diesen Beitrag antworten »

Stimmts also so wie ich es habe? Auf jeden Fall möchte ich mich an dieser Stelle für deine Hilfe und deine Geduld bedanken. smile

smile

Gruss FG

22.06.2011, 01:05

tigerbine

Auf diesen Beitrag antworten »

Rechnung scheint doch zu stimmen. Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »