Vollständige Induktion

03.10.2007, 11:01

_Vic_

Auf diesen Beitrag antworten »

Vollständige Induktion

Moin Moin,

wir sollen ein paar Aufgaben zur Induktion als Übung lösen. Da ich dieses Thema jedoch noch nie in der Schule hatte, habe ich mich im Internet ein wenig schlau gemacht. Dabei bin ich auf den Workshop hier im Forum gestoßen.

Nur bin ich mir nicht so sicher, ob das was ich zusammengerechnet habe, wirklich richtig ist.
Deshalb bitte ich um Ratschläge und Korrekturen.

Die Ausgangsformel:
$\begin{eqnarray*} \sum_{i=0}^n~i^{2}=\frac{1}{6}n(n+1)(2n+1) \end{eqnarray*}$

Da für i nichts angegeben wurde, gehe ich mal davon aus, dass
$\begin{eqnarray*} i\in \mathbb N \end{eqnarray*}$ ist

Induktionsanfang: n=0
$\begin{eqnarray*} \sum_{i=0}^0~i^{2}=\frac{1}{6}0(0+1)(2*0+1) \end{eqnarray*}$

Induktionsvoraussetzung $\begin{eqnarray*} n\geq 0 \end{eqnarray*}$

Induktionsschluss $\begin{eqnarray*} n\Rightarrow n+1 \end{eqnarray*}$
$\begin{eqnarray*} \sum_{i=0}^{n+1}~i^{2}= & \frac{1}{6}(n+1)(n+2)(2n+3) \\ \sum_{i=0}^{n+1}~i^{2}= & \frac{1}{3}n^3+\frac{3}{2}n^2+ \frac{13}{6}n+1 \end{eqnarray*}$

Nun addiere ich die Voraussetzung mit dem letzten Summanden
$\begin{eqnarray*} \sum_{i=0}^{n+1}~i^{2}= &\frac{1}{6}n(n+1)(2n+1) +(n+1)^2 \\ \sum_{i=0}^{n+1}~i^{2}= &\frac{1}{3}n^3+\frac{3}{2}n^2+ \frac{7}{3}n+1 \end{eqnarray*}$

Habe ich jetzt einen Fehler gemacht, oder ist damit bewiesen worden, dass die Behauptung nicht zutrifft?

Gruß

Vic

03.10.2007, 11:09

therisen

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von _Vic_
Da für i nichts angegeben wurde, gehe ich mal davon aus, dass
$\begin{eqnarray*} i\in \mathbb N \end{eqnarray*}$ ist

Das ist klar und braucht nicht angegeben zu werden.

Zitat:

Original von _Vic_
Induktionsvoraussetzung $\begin{eqnarray*} n\geq 0 \end{eqnarray*}$

Das ist nicht deine Induktionsvoraussetzung.

Zitat:

Original von _Vic_
Nun addiere ich die Voraussetzung mit dem letzten Summanden
$\begin{eqnarray*} \sum_{i=0}^{n+1}~i^{2}= &\frac{1}{6}n(n+1)(2n+1) +(n+1)^2 \\ \sum_{i=0}^{n+1}~i^{2}= &\frac{1}{3}n^3+\frac{3}{2}n^2+ \frac{7}{3}n+1 \end{eqnarray*}$

Dein Endergebnis ist falsch. Du hast dich also verrechnet.

Gruß, therisen

03.10.2007, 11:41

_Vic_

Auf diesen Beitrag antworten »

Wie muss die Voraussetzung dann aussehen?

[WS] Vollständige Induktion Hier im ersten Beispiel wurde das doch genau so gemacht.

03.10.2007, 11:44

marci_

Auf diesen Beitrag antworten »

überprüfe einfach, ob die aussage für das kleinste glied gilt...
in deinem falle: i=0 einsetzen und schauen, ob eine wahre aussageherauskommt...

03.10.2007, 11:47

_Vic_

Auf diesen Beitrag antworten »

Wenn ich i = 0 setze, dann bekomme ich doch

0 = 0

heraus, da 0² = 0 und 1/6 * 0 * 1 auch 0 ist.

Ah i in das Endergebnis einsetzen! Das habe ich in der Ausgangsformel gemacht.
Stimmt, du hast Recht! Da stimmt was nicht!

03.10.2007, 12:06

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von _Vic_
Wie muss die Voraussetzung dann aussehen?

Es fehlen die Worte "Es gelte" oder "Die Behauptung sei für ein $\begin{eqnarray*} n\geq0 \end{eqnarray*}$ richtig". Ein kleiner, aber feiner Unterschied.

Den Induktionsanfang hast du schon richtig gemacht.

Anzeige

03.10.2007, 12:14

_Vic_

Auf diesen Beitrag antworten »

So besser?
Bzw. jetzt muss ich nur noch den Rechenfehler finden.

Die Ausgangsformel:
$\begin{eqnarray*} \sum_{i=0}^n~i^{2}=\frac{1}{6}n(n+1)(2n+1) \end{eqnarray*}$

Da für i nichts angegeben wurde, gehe ich mal davon aus, dass
$\begin{eqnarray*} i\in \mathbb N \end{eqnarray*}$ ist

Induktionsanfang: Man zeige, dass n=0 gilt
$\begin{eqnarray*} \sum_{i=0}^0~i^{2}=\frac{1}{6}0(0+1)(2*0+1) \end{eqnarray*}$

Induktionsvoraussetzung Es gelte für ein $\begin{eqnarray*} n\geq 0 \end{eqnarray*}$

Induktionsschluss: Man schliesse von n auf n+1 $\begin{eqnarray*} n\Rightarrow n+1 \end{eqnarray*}$
$\begin{eqnarray*} \sum_{i=0}^{n+1}~i^{2}= & \frac{1}{6}(n+1)(n+2)(2n+3) \\ \sum_{i=0}^{n+1}~i^{2}= & \frac{1}{3}n^3+\frac{3}{2}n^2+ \frac{13}{6}n+1 \end{eqnarray*}$

Nun addiere ich die Voraussetzung mit dem letzten Summanden
$\begin{eqnarray*} \sum_{i=0}^{n+1}~i^{2}= &\frac{1}{6}n(n+1)(2n+1) +(n+1)^2 \\ \sum_{i=0}^{n+1}~i^{2}= &\frac{1}{3}n^3+\frac{3}{2}n^2+ \frac{13}{6}n+1 \end{eqnarray*}$

So, ich habe den Rechenfehler gefunden und korrigiert.

03.10.2007, 12:17

therisen

Auf diesen Beitrag antworten »

Du hast ja nur eine Formulierung ausgetauscht Augenzwinkern

Augenzwinkern

Der Fehler ist hier:

$\begin{eqnarray*} \frac{1}{6}n(n+1)(2n+1) +(n+1)^2\neq\frac{1}{3}n^3+\frac{3}{2}n^2+ \frac{7}{3}n+1 \end{eqnarray*}$

03.10.2007, 12:35

_Vic_

Auf diesen Beitrag antworten »

Ich habe das alles noch einmal nachgerechnet und den Rechenfehler gefunden.
Jetzt sind beide Ergebnisse identisch.

Heisst das jetzt, dass die Behauptung bewiesen wurde?
Bzw. ich möchte auf Marci's Einwand nochmal zu sprechen kommen.
Wenn ich für i = 0 einsetze, dann bekomm ich doch auf der rechten Seite 1 heraus.

Eine Erklärung wäre vllt. nicht verkehrt. Wie gesagt, ich hatte das Thema nie in der Schule :/

Gruß

Vic

03.10.2007, 12:38

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von _Vic_
Heisst das jetzt, dass die Behauptung bewiesen wurde?

Ja.

Zitat:

Original von _Vic_
Bzw. ich möchte auf Marci's Einwand nochmal zu sprechen kommen.
Wenn ich für i = 0 einsetze, dann bekomm ich doch auf der rechten Seite 1 heraus.

Erstens setzt du eigentlich n=0 ein, zweitens kommt auf beiden Seiten 0 heraus.

03.10.2007, 13:07

Airblader

Auf diesen Beitrag antworten »

...und zwar schon deshalb, weil ein n als Faktor auftritt. Und wird ein Faktor 0, so ist das gesamte Produkt 0.

air

03.10.2007, 13:25

_Vic_

Auf diesen Beitrag antworten »

Ahh, moment, ich war bei der falschen Formel!
Ich habe im Ergebnis n auf 0 gesetzt. Und durch das +1 kam 1 heraus.
Danke für eure Hilfe, ich glaube dass ich das Thema jetzt im Groben verstanden habe!

08.10.2007, 18:03

versucher3000

Auf diesen Beitrag antworten »

Hallo, ich hab mich jetzt auch mal an dem Thema versucht. Ist meine Lösung auch richtig? Auch von den Begrifflichkeiten?

Induktionsvorrausetzung:
$\begin{eqnarray*} \sum_{i=0}^n~i^2 = \frac{1}{6}*n*(n+1)*(2n+1) \end{eqnarray*}$

Induktionsbasis: 0 einsetzen, beide Seiten der Gleichung werden 0, Induktionsbasis ist erfüllt.

Induktionsschritt
Ich lasse die Summenformel nur bis n-1 laufen und addiere dazu n-Quadrat, was dann wieder dasselbe ist wie auf der rechten Seite der Gleichung (über dem Summenzeichen steht noch n, ich weiß nicht wie ich da n-1 hinbekomme):

$\begin{eqnarray*} (\sum_{i=0}^n~i^2)+n^2 = \frac{1}{6}*n*(n+1)*(2n+1) \end{eqnarray*}$

Da die Summenformel in Klammern ja im Prinzip nichts andere ist als die Gleichung auf der rechten Seite, bloß halt mit n-1, darf ich eben diese anstatt der Summenformel dorthinschreiben:

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

Da kann ich n ja schonmal wegkürzen. Vereinfache ich weiter lande ich am Ende bei $\begin{eqnarray*} n=n \end{eqnarray*}$ , womit ich denke die Behauptung bewiesen zu haben.

Ist das so richtig Hammer

Hammer

08.10.2007, 18:09

therisen

Auf diesen Beitrag antworten »

Wieso schreibst du die Induktionsvorrausetzung vor die Induktionsbasis?

Dein Beweis ist im Prinzip richtig, aber volle Punktzahl wirst du auf diesen Beweis nicht bekommen. Ganz einfach deshalb, weil er unsauber aufgeschrieben ist Augenzwinkern

Augenzwinkern

Gruß, therisen

08.10.2007, 18:23

ThLu

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
warum wird bei der voraussetzung $\begin{eqnarray*} (n+1)^2 \end{eqnarray*}$ dazuaddiert?

08.10.2007, 18:53

versucher3000

Auf diesen Beitrag antworten »

Okay, bei der folgenden Aufgabe hab ich keine so rechte Idee:

$\begin{eqnarray*} 2^n>n \end{eqnarray*}$ für alle n > 0

Draus mache ich

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

War's das schon? Ich wüsste nicht was ich jetzt noch machen sollte, zumal je größer n wird die Rechte Seite der Gleichung immer kleiner, die linke immer größer wird verwirrt

verwirrt

08.10.2007, 19:52

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von versucher3000
Induktionsschritt
Ich lasse die Summenformel nur bis n-1 laufen und addiere dazu n-Quadrat, was dann wieder dasselbe ist wie auf der rechten Seite der Gleichung (über dem Summenzeichen steht noch n, ich weiß nicht wie ich da n-1 hinbekomme):

$\begin{eqnarray*} (\sum_{i=0}^n~i^2)+n^2 = \frac{1}{6}*n*(n+1)*(2n+1) \end{eqnarray*}$

Ich halte das für methodisch nicht so geschickt. Denn das:

$\begin{eqnarray*} \sum_{i=0}^n~i^2 = \frac{1}{6}*n*(n+1)*(2n+1) \end{eqnarray*}$

ist die zu zeigende Aussage und demzufolge beim Induktionsschritt die Induktionsvoraussetzung.

Was die Ungleichung $\begin{eqnarray*} 2^n > n \end{eqnarray*}$ angeht, ist es erstmal das beste, daß du sauber die einzelnen Teile des Beweises hinschreibst. Sprich:
Was ist die Behauptung?
Was ist der Induktionsanfang?
Was ist beim Induktionsschritt die Induktionsvoraussetzung?
Was ist beim Induktionsschritt das Induktionsziel?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »