Formalismus bei der vollständigen Induktion

25.04.2012, 10:03

Tanzender Barde

Formalismus bei der vollständigen Induktion

Schönen guten Tag zusammen!

Allem Anschein nach habe ich mir das Prinzip der vollständigen Induktion falsch eingelernt. Und zwar gehe ich wie folgt vor:

1) Zuerst kommt der Induktionsanfang, der ist meist sehr trivial. Damit beweise ich ob die Voraussetzung überhaupt gilt, also ob die Gleichung für die Summe/das Produkt bis n überhaupt gültig ist.

2) Danach stelle ich die Behauptung auf. Alle n werden auf n+1 abgebildet. (n -> n+1)

3) Zuletzt bleibt noch der oftmals komplexe Induktionsschritt, also der Beweis für n+1 (und hier passiert allem Anschein nach der formale Fehler, auch wenn das Ergebnis meist korrekt ist)

Ich ging hier bisher wie folgt vor: (ein Beispiel zur Veranschaulichung)
$\begin{eqnarray*} \sum_{i = 0}^{n} (i+1)(i-1) = \frac{1}{6}n(n-1)(2n+5) \end{eqnarray*}$

I.A. j=1, j=1:

$\begin{eqnarray*} (1+1)*(1-1) = \frac{1}{6}*1*(1-1)*(2+5) \end{eqnarray*}$
$\begin{eqnarray*} 0 = 0 \end{eqnarray*}$ w.A.

I.B.
$\begin{eqnarray*} \sum_{i=0}^{n+1} (i+1)(i-1) = \frac{1}{6} (n+1)n(2(n+1)+5) \end{eqnarray*}$

I.S.
$\begin{eqnarray*} \sum_{i=0}^{n+1} (i+1)(i-1) = \sum_{i=0}^{n} (i+1)(i-1) + (n+2)(n) \end{eqnarray*}$

Links würde ich die Gleichung jetzt durch die Behauptung ersetzen und links die Summe durch die rechte Seite der Induktionsvoraussetzung. (Diese wurde ja schon bewiesen) (Vielleicht ist genau das auch formal nicht ganz korrekt? Weil ich hier die rechte Seite der Behauptung schon einsetze? Ich finde es beim Umformen einfach bequemer, weil ich so auf beiden Seiten die selben Operationen durchführen kann ohne am Ende nochmal die Behauptung seperat umformen zu müssen)

Das würde dann so aussehen:

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

Und nach ein wenig Ausmultiplizieren und Umformen kämen wir auf:

$\begin{eqnarray*} 2n^2 + 9n + 7 = 2n^2 + 9n + 7 \end{eqnarray*}$

also eine an sich wahre Aussage.

Jetzt meinten einige KollegInnen, dass es bei mir so aussehen würde als wolle ich ganz allgemein die triviale Gleichung
$\begin{eqnarray*} \sum_{i=0}^{n+1} ... = \sum_{i=0}^{n} + (n+1tes Glied) \end{eqnarray*}$
beweisen und das wäre formal ja nicht korrekt.

Da ich mir das Ganze anscheinend falsch eingelernt habe hier meine Frage: Wo genau passiert hier der Fehler und wie kann ich ihn umgehen? Denken tue ich meiner Meinung nach ja richtig, nur formal stimmt es eben nicht so ganz. Dafür Punkteabzug bei der Klausur zu bekommen wäre allerdings traurig unglücklich

Freundliche Grüße
Tanzender Barde

25.04.2012, 10:55

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Tanzender Barde
$\begin{eqnarray*} \sum_{i = 0}^{n} (i+1)(i-1) = \frac{1}{6}n(n-1)(2n+5) \end{eqnarray*}$

Diese Behauptung ist falsch. Wenn du sie allerdings zu

$\begin{eqnarray*} \sum_{i={\color{red}1}}^{n} (i+1)(i-1) = \frac{1}{6}n(n-1)(2n+5) \end{eqnarray*}$

korrigierst, dann ist sie in Ordnung.

25.04.2012, 11:08

Tanzender Barde

Auf diesen Beitrag antworten »

Entschuldige, ich kann leider nicht mehr editieren, aber das stimmt natürlich. Die Summe geht von 1 weg.

Ansonsten, passt der Weg?

25.04.2012, 11:39

HAL 9000

Auf diesen Beitrag antworten »

Grundsätzlich zum Vorgehen:

Du hast sowohl Induktionsvoraussetzung als auch Induktionsbehauptung eingesetzt und kommst dann zu einer für alle $\begin{eqnarray*} n \end{eqnarray*}$ gültigen Gleichung, also einer wahren Aussage. Das ist prinzipiell schon in Ordnung, wird allerdings mancherorts nicht gern gesehen, wenn dabei die Rechtmäßigkeit dieses Vorgehens nicht ausreichend klargestellt wird. Daher fährt man mit einem Induktionsschritt strukturiert wie

$\begin{eqnarray*} \sum_{i=0}^{n+1} (i+1)(i-1) = \sum_{i=0}^{n} (i+1)(i-1) + (n+2)n \stackrel{IV}{=} \frac{n(n-1)(2n+5)}{6} + (n+2)n \stackrel{U}{=} \frac{(n+1)n(2n+7)}{6} \end{eqnarray*}$

in der Regel besser (IV = Induktionsvoraussetzung, U = algebraische Umformung). Auch und gerade, wenn man etwa eine Ungleichung beweist, denn Vollständige Induktion ist ja zu weit mehr tauglich als nur zu Beweisen irgendwelcher Summenformeln. Augenzwinkern

25.04.2012, 11:45

klarsoweit

Auf diesen Beitrag antworten »

RE: Formalismus bei der vollständigen Induktion

Zitat:

Original von Tanzender Barde
1) Zuerst kommt der Induktionsanfang, der ist meist sehr trivial. Damit beweise ich ob die Voraussetzung überhaupt gilt, also ob die Gleichung für die Summe/das Produkt bis n überhaupt gültig ist.

Da fängt das Mißverständnis schon an. Beim Induktionsanfang zeigst du, daß die Behauptung für einen ganz bestimmten Wert von n (meistens n=1, kann aber auch was anderes sein) gilt.

Zitat:

Original von Tanzender Barde
I.B.
$\begin{eqnarray*} \sum_{i=0}^{n+1} (i+1)(i-1) = \frac{1}{6} (n+1)n(2(n+1)+5) \end{eqnarray*}$

I.S.
$\begin{eqnarray*} \sum_{i=0}^{n+1} (i+1)(i-1) = \sum_{i=0}^{n} (i+1)(i-1) + (n+2)(n) \end{eqnarray*}$

Auch das ist eher von formalen Mißverständnissen geprägt.

Im Induktionsschritt wird angenommen, daß die Behauptung für ein beliebiges n gilt, und es wird dann gezeigt, daß die Behauptung für n+1 gilt. Für diese Aufgabe lautet also der Induktionsschritt:

IS:
Unter der Annahme, daß

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

gilt, ist zu zeigen, daß auch

(B) $\begin{eqnarray*} \sum_{i=1}^{n+1} (i+1)(i-1) = \frac{1}{6} (n+1)n(2(n+1)+5) \end{eqnarray*}$ gilt.

Meistens (aber es ist nicht gesagt, daß das immer so funktioniert) nimmt man die linke Seite von B und formt die so um, daß man die Induktionsannahme A verwenden kann. Also:

(C) $\begin{eqnarray*} \sum_{i=1}^{n+1} (i+1)(i-1) = \sum_{i=1}^n (i+1)(i-1) + (n+2)n \end{eqnarray*}$

Nach Einsetzen der Induktionsannahme (A) in die rechte Seite von (C) muß man nur noch schauen, daß diese gleich der rechten Seite von (B) ist.

Im Prinzip hast du das mit deiner Rechnung auch gemacht. Es wird aber formal nicht so ganz klar, was du warum gemacht hast. Bei mir würde das in jedem Fall Abzüge in der B-Note geben. smile

EDIT: jetzt war HAL9000 schneller, aber ich lasse meins trotzdem mal stehen. traurig

25.04.2012, 11:58

Tanzender Barde

Auf diesen Beitrag antworten »

@HAL 9000: Dankeschön. Also im Endeffekt sollen IV und U klarstellen, dass ich weiß was ich tue, was aus meinem Weg anscheinend nicht ganz so rüberkommt?

Zitat:

Original von klarsoweit

Zitat:

Da fängt das Mißverständnis schon an. Beim Induktionsanfang zeigst du, daß die Behauptung für einen ganz bestimmten Wert von n (meistens n=1, kann aber auch was anderes sein) gilt.

Entschuldige, das stimmt natürlich. Ich setze ja konkret einen Wert ein was bedeutet, dass es auch erstmal nur für genau diesen gilt. (Der Anfang kann ja verschoben sein, also für die Werte 1-7 gilt die Behauptung nicht, für 8 aber schon. Dann möchte man ja beweisen, dass es ab 8 für alle weiteren natürlichen Zahlen gilt)

Zitat:

Original von klarsoweit

Zitat:

Verdammt, ich seh den formalen Unterschied einfach nicht. Liegt es daran, dass ich bei (C) für die linke Seite gleich die rechte Seite von B einsetze oder darf ich das? (Es ist ja nur eine Behauptung).

Wie du sagst, im Grunde mache ich genau das, aber irgendwo ist da der Wurm drinnen... in meiner eingefahrenen Denkweise stimmt es ja und auch die Ergebnisse sind meistens korrekt.

Jetzt muss ich noch zusehen, dass ich den Unterschied zwischen euren Aussagen und der meinigen begreife.

25.04.2012, 12:41

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Tanzender Barde
Verdammt, ich seh den formalen Unterschied einfach nicht. Liegt es daran, dass ich bei (C) für die linke Seite gleich die rechte Seite von B einsetze oder darf ich das? (Es ist ja nur eine Behauptung).

In gewisser Weise ja. Dadurch entsteht aus einer wahren Aussage, was (C) zweifelsohne ist, eine Aussage, deren Wahrheitsgehalt man nicht kennt. Mit Äquivalenzumformungen mußt du dann zeigen daß diese wahr. Wie gesagt: man kann das so machen, muß dann aber darauf achten, daß man tatsächlich auch Äquivalenzumformungen vorgenommen hat. Ich finde, eine Gleichungskette, mit der man zeigt, daß X = Y ist, ist einfach praktischer.

25.04.2012, 13:40

Tanzender Barde

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit

Zitat:

Also, nur damit ich das richtig verstehe.

Mit Gleichungskette meinst du anstatt im Induktionsschritt auch die linke Seite durch die Behauptung zu ersetzen würdest du die Behauptung gar nicht einbauen und versuchen so umzuformen, dass du am Ende die Behauptung rauskriegst? (also da steht dann nicht a = a sondern Summe... = a und bei der Behauptung eben das selbe)

Falls ja, dann ist das teilweise etwas kompliziert, weil man die Behauptung am Ende dann nochmal umformen muss, damit sie auf den ersten Blick mit der Lösung des Induktionsschlußes zusammenpasst.

Mich verunsichert das immer ein wenig, weshalb ich es halt einfach recht praktisch fand gleichzusetzen und auf beiden Seiten äquivalent umzuformen.

Hab ich deine Aussage so jetzt richtig interpretiert?

28.04.2012, 10:11

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Tanzender Barde
Mich verunsichert das immer ein wenig, weshalb ich es halt einfach recht praktisch fand gleichzusetzen und auf beiden Seiten äquivalent umzuformen.

Mein Vorschlag: Wenn du so eine pons asini wirklich brauchst *), so mach das doch in einer Nebenrechnung, die du dann bei der einer schriftlichenn Prüfung dick durchstreichst bzw. hier im Forum erst gar nicht präsentierst, und mach dann daraus in der "Endfassung" eine Gleichungskette bzw. Schlusskette...

*) Insgesamt sollte es natürlich dein Ziel sein, durch sehr viel Übung solche Eselsbrücken überhaupt entbehrlich zu machen... Augenzwinkern

Neue Frage »

Antworten »

Formalismus bei der vollständigen Induktion

Verwandte Themen