Vollständige Induktion - wo ist der Beweis?

Nils Wrase · 3 September 2009

Vollständige Induktion - wo ist der Beweis?

Hallo Leute, wer eifrig hier im Forum aktiv ist hat sicherlich schon mitbekommen, dass mir das Prinzip der vollständigen Induktion irgendwie noch unklar ist. Ich will hier auch niemandem auf den Senkel gehen, trotzdem habe ich beim weiteren Durchgehen der vom Lehrstuhl zur Verfügung gestellten Aufgaben bei der nächsten Aufgabe zum diesem Thema wieder das gleiche Problem. Ich kann inzwischen die Umformungsschritte der Musterlösungen nachvollziehen und es ist mir auch inzwischen egal, ob der Beweis nun über n+1 oder n-1 gesucht wird. Was mir aber immer noch unklar ist, ist, warum das Ganze eigentlich ein Beweis sein soll.

Also das nächste Beispiel: Aufgabe zu den Studientagen aus dem Infoheft zur KE 3 Aufgabe 2a) - die gleiche Aufgabe ist aber auch das erste Beispiel im Teschl zum Thema:

Beweisen Sie: [tex] \sum_{i=1}^n i = \frac{n(n+1)}2[/tex]

Als Induktionsanfang wird dann n = 0 präsentiert, was ja auch nachvollziebar 0 = 0 ergibt (Wobei sich mir hier schon die Frage stellt: Wieso n=0 ? Denn der kleinste Wert für n soll ja eigentlich 1 sein, aber das ist ja vermutlich das kleinste Problem).

Konkret bewiesen ist damit:

[tex] \sum_{i=0}^{n=0} i = \frac{0(0+1)}2[/tex]

Der Induktionsanfang ist das Einzige, was meiner Meinung nach bewiesen ist, im Verlauf der weiteren Umformungen wird darauf nie wieder Bezug genommen, so dass ich mir auch die Frage stelle, warum man sich diesen Induktionsanfang dann nicht gleich schenkt.

Weiter geht es: Die Induktionsvoraussetzung wird aufgestellt, für beide Seiten des Gleichheitszeichens geht man auf n-1:

[tex]\sum_{i=1}^{n-1} i = \frac{(n-1)n} 2 [/tex]

Das dies so sei, ist aber ja nicht bewiesen, wird nicht bewiesen und steht für mich auch in keinem erkennbaren Zusammenhang zu dem bewiesenen Induktionsanfang. Entwickelt wird es ja aus der zu beweisenden Ausgangsaussage, nicht aus dem bewiesenen Induktionsanfang.

So, dann stellen sie fest:

[tex] \sum_{i=1}^n i = \sum_{i=1}^{n-1} i + n[/tex]

Für mich ok, ändert aber nichts und beweist auch nichts.

Weiter stellen sie fest:

[tex]\sum_{i=1}^{n-1} i + n = \frac{(n-1)n} 2 + \frac{2n} 2[/tex]

Was ist da also passiert? Man hat zur unbewiesenen Induktionsvoraussetzung auf beiden Seiten n addiert. Jetzt stellen sie dann noch fest, dass die rechte Seite ungeformt nichts anderes ist als

[tex] \frac{n(n+1)}2[/tex] was insgesamt eigentlich bewiesen werden sollte.

Wo ist da jetzt eigentlich der Beweis? Man hat doch nichts weiter getan, als Folgendes: Zum aufstellen der Induktionsvoraussetzung hatte man die zu beweisende Ausgangsaussage von n auf n-1 gesetzt. Damit ist sie aber ja keineswegs bewiesen. Dann hat man wieder n addiert. Nun stellt man fest: Donnerwetter, wir sind wieder bei n. So stelle ich mir keine Beweisführung vor.

Die Induktionsvoraussetzung ist für mich nicht bewiesen. Wenn man da auf beiden Seiten n addiert und sich daraus dann die zu beweisende Ausgangsaussage ergibt, ist das für mich kein Beweis dafür, dass die Ausgangsaussage richtig war.

Für mich wäre es plausibel, dass es bewiesen wäre, wenn an irgendeiner Stelle in die Induktionsvoraussetzung der bewiesene Induktionsanfang eingesetzt würde. Irgendwofür muss der ja auch gut sein. Das ist aber ja nicht der Fall. Zumindest kann ich das nicht erkennen.

Für sachdienliche Hinweise wäre ich dankbar.

Gruß, Nils

chris* · 3 September 2009

Nils Wrase schrieb:
Hallo Leute, wer eifrig hier im Forum aktiv ist hat sicherlich schon mitbekommen, dass mir das Prinzip der vollständigen Induktion irgendwie noch unklar ist. Ich will hier auch niemandem auf den Senkel gehen

Soll ich mich da jetzt angesprochen fühlen? 😉 Die Klausur ist inzwischen vorbei, also auf gehts.

Was mir aber immer noch unklar ist, ist, warum das Ganze eigentlich ein Beweis sein soll.

Mal mathematisch formuliert: Das Induktionsprinzip ist ein Axiom. Axiome sind Sätze, die man als wahr postuliert, ohne sie zu beweisen. Warum funktioniert das? Im Unterschied zur Physik, wo es eine beobachtbare Realität gibt, die man mit einer Theorie möglichst korrekt beschreiben möchte, gibt es in der Mathematik so etwas nicht. Wir haben zwar eine intuitive Vorstellung von natürlichen Zahlen (drei Äpfel plus zwei Äpfel sind fünf Äpfel), aber was man in der modernen Mathematik wirklich haben will ist eine axiomatische Beschreibung eines Begriffs. Das heißt, man definiert z.B. die natürlichen Zahlen nicht direkt, sondern über eine Reihe von Axiomen, und wenn diese Axiome sich nicht gegenseitig widersprechen, dann gibt es irgendwelche Objekte, die diese Axiome erfüllen. Im Falle der natürlichen Zahlen geht es um die Peano-Axiome (hier schamlos, aber frei aus Wikipedia geklaut):

1. 0 ist eine natürliche Zahl
2. Jede natürliche Zahl n hat genau einen Nachfolger n', der ebenfalls natürliche Zahl ist.
3. 0 ist nicht Nachfolger einer natürlichen Zahl.
4. Jede natürliche Zahl ist Nachfolger höchstens einer natürlichen Zahl.
5. (Induktionsaxiom) Von allen Mengen X, welche die 0 und zu jeder natürlichen Zahl auch stets ihren Nachfolger enthalten, ist die Menge der natürlichen Zahlen die kleinste. (Das "kleinste" ist hier so zu verstehen, dass die Menge der natürlichen Zahlen der Durchschnitt aller dieser Mengen X ist, d.h. sie ist Teilmenge von allen diesen Mengen).

So und jetzt haben wir eine Aussage A(n) und eine Behauptung "A(n) gilt für alle natürlichen Zahlen n". Betrachten wir das mal aus einem anderen Blickwinkel: Wenn M die Menge der Objekte n ist, für die A(n) wahr ist, dann wollen wir zeigen, dass alle natürlichen Zahlen in M enthalten sind. Damit kommt das Induktionsaxiom ins Spiel: Wenn M also die 0 und zu jeder natürlichen Zahl ihren Nachfolger enthält, dann gehört M zu dieser Klasse von Mengen, deren kleinste die Menge der natürlichen Zahlen ist, also ist N Teilmenge von M. Mit anderen Worten, der Beweis besteht aus zwei Teilen:

1) Zeige, dass 0 in M enthalten ist. [Induktionsanfang: Zeige A(0)]
2) Zeige, dass für jede natürliche Zahl n auch ihre Nachfolger n' in M enthalten ist [Induktionsschritt: Zeige A(n) -> A(n+1)]

Und das wars. Variationen, die sich auf dieses Prinzip zurückführen lassen:
- Man kann natürlich auch Aussagen, die nicht ab 0 sondern ab einer anderen Zahl für alle weiteren natürlichen Zahlen gelten, so umformulieren, dass sie ab 0 gelten.
- Man kann die Variable n substituieren und A(n-1) -> A(n) beweisen
- es gibt die Vollständige Induktion, bei der man A(0) und A(1) und ... und A(n) -> A(n+1) beweist

Soweit zum mathematischen, alles weitere kann einem das Induktionsprinzip höchstens plausibler machen, aber nicht stringent begründen.

Als Induktionsanfang wird dann n = 0 präsentiert, was ja auch nachvollziebar 0 = 0 ergibt (Wobei sich mir hier schon die Frage stellt: Wieso n=0 ? Denn der kleinste Wert für n soll ja eigentlich 1 sein, aber das ist ja vermutlich das kleinste Problem).

Kommt auf den Kurs an, ist in 1142 0 oder 1 als kleinste natürliche Zahl definiert? Wenn 1, dann ist das hier Schlampigkeit, dann müsste man den Induktionsanfang mit 1 machen.

Der Induktionsanfang ist das Einzige, was meiner Meinung nach bewiesen ist, im Verlauf der weiteren Umformungen wird darauf nie wieder Bezug genommen, so dass ich mir auch die Frage stelle, warum man sich diesen Induktionsanfang dann nicht gleich schenkt.

Wenn man den Beweis vollständig und korrekt aufschreibt, müsste man nach Induktionsanfang und -schritt noch ein Sprüchlein der Art "Die Behauptung ergibt sich nun nach dem Induktionsprinzip aus dem Induktionsanfang und dem Induktionssschritt" oder so aufsagen (in der Schule musste wir das damals immer), aber wer schonmal was von Induktion gehört hat kennt das und es wird irgendwann langweilig. Normalerweise steht also am Anfang des Beweises sowas wie "Induktion nach n" und damit ist alles klar, der Bezug auf den Induktionsanfang ist dann implizit.

Weiter geht es: Die Induktionsvoraussetzung wird aufgestellt, für beide Seiten des Gleichheitszeichens geht man auf n-1:

[tex]\sum_{i=1}^{n-1} i = \frac{(n-1)n} 2 [/tex]

Das dies so sei, ist aber ja nicht bewiesen, wird nicht bewiesen und steht für mich auch in keinem erkennbaren Zusammenhang zu dem bewiesenen Induktionsanfang.

Richtig, es gibt diesen Zusammenhang nicht. Induktionsanfang und -schritt sind zwei vollkommen getrennte Teilbeweise.

Behauptet wird im Induktionsschritt "A(n-1) -> A(n)", also in Worten "Wenn A für eine Zahl n-1 gilt, dann gilt sie zwingend auch für den Nachfolger n". Um das zu beweisen, nimmt man A(n-1) als Voraussetzung an und zeigt auf der Basis A(n).
Die Induktionsvoraussetzung muss man und kann man nicht beweisen. Das tut man bei keinem Beweis, deshalb ist es ja die Voraussetzung und nicht die Behauptung. Der Satz des Pythagoras z.B. hat die Voraussetzung, dass das Dreieck rechtwinklig ist. Das beweist man ja auch nicht.

Wo ist da jetzt eigentlich der Beweis? Man hat doch nichts weiter getan, als Folgendes: Zum aufstellen der Induktionsvoraussetzung hatte man die zu beweisende Ausgangsaussage von n auf n-1 gesetzt.

Das stimmt nicht. Die Anfangsaussage ist "A gilt für alle natürlichen Zahlen n", und die Induktionsvoraussetzung ist "A gilt für eine ganz bestimmte, aber sonst unbekannte natürliche Zahl n".
Dass es so eine Zahl gibt, erfährt man im Induktionsanfang, deshalb gehört der dazu, aber das muss einen im Induktionsschritt nicht interessieren. Sollte es sich herausstellen, dass es so eine Zahl nicht gibt, dann ist der Induktionsschritt für sich immer noch richtig. Aber halt insgesamt wertlos 😉

Für mich wäre es plausibel, dass es bewiesen wäre, wenn an irgendeiner Stelle in die Induktionsvoraussetzung der bewiesene Induktionsanfang eingesetzt würde. Irgendwofür muss der ja auch gut sein. Das ist aber ja nicht der Fall. Zumindest kann ich das nicht erkennen.

Das kann man schon machen. Man stellt sich den Beweis als unendliche Kette vor. Man weiß ja, dass die Aussage für n=0 gilt. Wenn man das in den Induktionsschritt einsetzt, erhält man die Aussage für n=1. Setzt man das wieder ein, bekommt man sie für n=2, und so weiter.
Das fettgedruckte ist das eigentlich wesentliche bei der Induktion. Eigentlich immer, wenn man irgendwas mit "und so weiter" begründen will, versteckt sich dahinter eine Induktion. Ich wende den Gedanken mal auf die obige Aussage an. Behauptet war [tex]1+\cdots+n = \frac{n(n+1)}{2}[/tex]. Für n=1 heißt das also [tex]1 = \frac{1\cdot 2}{2} = 1[/tex], für n=2 heißt es [tex]1 + 2 = \frac{1 \cdot 2}{2} + 2 = \frac{1 \cdot 2}{2} + \frac{2\cdot 2}{2} = \frac{2(1+2)}{2} = 3[/tex], für n=3 heißt es [tex]1+2+3 = \frac{2(1+2)}{2} + 3 = \frac{2\cdot 3}{2}+ \frac{2\cdot 3}{2} = \frac{3(2+2)}{2} = \frac{3\cdot 4}{2} = 6[/tex], und jetzt immer so weiter. Man kann das ja schlecht alles bis in die Unendlichkeit aufschreiben, aber ein "und so weiter" glaubt man auch nicht einfach so, und genau dafür gibt es Induktion.

Nils Wrase · 4 September 2009

chris*,

erstmal vielen Dank für deine Mühe! Du hast dir ja richtig viel Arbeit gemacht, das ist echt nett!

chris* schrieb:
Soll ich mich da jetzt angesprochen fühlen?

Außer dir scheint sich auch keiner so richtig da dran zu trauen, würde ich mal sagen...

chris* schrieb:
Mal mathematisch formuliert: Das Induktionsprinzip ist ein Axiom. Axiome sind Sätze, die man als wahr postuliert, ohne sie zu beweisen. Warum funktioniert das? Im Unterschied zur Physik, wo es eine beobachtbare Realität gibt, die man mit einer Theorie möglichst korrekt beschreiben möchte, gibt es in der Mathematik so etwas nicht. Wir haben zwar eine intuitive Vorstellung von natürlichen Zahlen (drei Äpfel plus zwei Äpfel sind fünf Äpfel), aber was man in der modernen Mathematik wirklich haben will ist eine axiomatische Beschreibung eines Begriffs. Das heißt, man definiert z.B. die natürlichen Zahlen nicht direkt, sondern über eine Reihe von Axiomen, und wenn diese Axiome sich nicht gegenseitig widersprechen, dann gibt es irgendwelche Objekte, die diese Axiome erfüllen.

Du hast dir da ja richtig Gedanken zur Wissenschaftstheorie und Methodik gemacht. Das finde ich super. Als ich noch hauptberuflich studierte, habe ich das auch gerne gemacht; seit ich berufstätig bin, komme ich da gar nicht mehr zu. Und leider habe ich da nicht Mathematik studiert. Nur so kann man eigentlich verstehen, was man tut. Aber es braucht viel mehr Zeit, als man hat.

chris* schrieb:
So und jetzt haben wir eine Aussage A(n) und eine Behauptung "A(n) gilt für alle natürlichen Zahlen n". Betrachten wir das mal aus einem anderen Blickwinkel: Wenn M die Menge der Objekte n ist, für die A(n) wahr ist, dann wollen wir zeigen, dass alle natürlichen Zahlen in M enthalten sind. Damit kommt das Induktionsaxiom ins Spiel: Wenn M also die 0 und zu jeder natürlichen Zahl ihren Nachfolger enthält, dann gehört M zu dieser Klasse von Mengen, deren kleinste die Menge der natürlichen Zahlen ist, also ist N Teilmenge von M. Mit anderen Worten, der Beweis besteht aus zwei Teilen:

1) Zeige, dass 0 in M enthalten ist. [Induktionsanfang: Zeige A(0)]
2) Zeige, dass für jede natürliche Zahl n auch ihre Nachfolger n' in M enthalten ist [Induktionsschritt: Zeige A(n) -> A(n+1)]

chris* schrieb:
Richtig, es gibt diesen Zusammenhang nicht. Induktionsanfang und -schritt sind zwei vollkommen getrennte Teilbeweise.

Behauptet wird im Induktionsschritt "A(n-1) -> A(n)", also in Worten "Wenn A für eine Zahl n-1 gilt, dann gilt sie zwingend auch für den Nachfolger n". Um das zu beweisen, nimmt man A(n-1) als Voraussetzung an und zeigt auf der Basis A(n).

Genau über die beiden Punkte muss ich nochmal nachdenken. Mir fällt das schwer, das in der Musterlösung zu finden.

chris* schrieb:
Kommt auf den Kurs an, ist in 1142 0 oder 1 als kleinste natürliche Zahl definiert? Wenn 1, dann ist das hier Schlampigkeit, dann müsste man den Induktionsanfang mit 1 machen.

Die Null ist schon als kleinste natürlich Zahl definiert in dem Kurs. Aber am Summenzeichen steht ja "von i=1 bis n". Wahrscheinlich ein Druckfehler.

chris* schrieb:
Wenn man den Beweis vollständig und korrekt aufschreibt, müsste man nach Induktionsanfang und -schritt noch ein Sprüchlein der Art "Die Behauptung ergibt sich nun nach dem Induktionsprinzip aus dem Induktionsanfang und dem Induktionssschritt" oder so aufsagen (in der Schule musste wir das damals immer), aber wer schonmal was von Induktion gehört hat kennt das und es wird irgendwann langweilig. Normalerweise steht also am Anfang des Beweises sowas wie "Induktion nach n" und damit ist alles klar, der Bezug auf den Induktionsanfang ist dann implizit.

Du hast das im ernst schon in der Schule gemacht? Kommst du aus China?

Ok, vielen Dank erstmal, ich muss das nun in Ruhe durchgehen.

Gruß, Nils

chris* · 6 September 2009

Nils Wrase schrieb:
Die Null ist schon als kleinste natürlich Zahl definiert in dem Kurs. Aber am Summenzeichen steht ja "von i=1 bis n". Wahrscheinlich ein Druckfehler.

Achso. [tex]\sum_{i=1}^0 a_i[/tex] ist schon eine sinnvolle Formulierung, i läuft dann halt über eine leere Indexmenge. Der Wert einer leeren Summe ist per Definition 0. (Der Wert eines leeren Produkts [tex]\prod_{i=1}^0 a_i[/tex]ist übrigens 1. Jeweils das neutrale Element.)

Du hast das im ernst schon in der Schule gemacht? Kommst du aus China?

Fast.

Fratz · 7 September 2009

chris* schrieb:
(hier schamlos, aber frei aus Wikipedia geklaut):

1. 0 ist eine natürliche Zahl

Wie meinen?

Nils Wrase · 7 September 2009

chris* schrieb:
Achso. [tex]\sum_{i=1}^0 a_i[/tex] ist schon eine sinnvolle Formulierung, i läuft dann halt über eine leere Indexmenge. Der Wert einer leeren Summe ist per Definition 0. (Der Wert eines leeren Produkts [tex]\prod_{i=1}^0 a_i[/tex]ist übrigens 1. Jeweils das neutrale Element.)

Ok, jetzt wo du das sagst, kann ich das auch nachvollziehen.

chris* schrieb:
Fast.

Ich wusste es! Da kann man dir ja nur gratulieren.

Thorkel · 8 September 2009

Also das Prinzip ist m.E.:
Beim Induktionsanfang überprüft man, daß die Aussage überhaupt für irgendein n erfüllt ist. Hier ist es für n=0 erfüllt.
Dann versucht man, abstrakt herzuleiten, daß es, nachdem es für n funktioniert hat, auch für n-1 funktioniert. Da es hier gelingt, die n-1 Ausdruck so umzuformen, daß im Prinzip wieder der Anfangsausdruck herauskommt, kann man daraus schliessen, daß dieser für alle n gilt, denn:
Es funktioniert für n, es funktioniert für n-1 (da derselbe Ausdruck nach Umformung), demnach funktioniert es auch wieder für (n-1)-1 etc., also letztlich für alle n.

Naja, ob das so toll erklärt ist ...

Das kennst Du vermutlich schon:
Das Prinzip der Vollständigen Induktion

Nils Wrase · 9 September 2009

Thorkel,

danke für den Link, werde ich mir mal in Ruhe durchlesen.

Gruß, Nils

Fratz · 9 September 2009

Ich habe noch NIE gelesen, dass man die Aussage für n behauptet und für n-1 beweist. Das würde nämlich heißen, dass wenn ich bei n=0 anfange es für alle negativen ganzen Zahlen und 0 bewiesen wäre, nicht aber für alle natürlichen Zahlen.

Thorkel schrieb:
Es funktioniert für n, es funktioniert für n-1 (da derselbe Ausdruck nach Umformung), demnach funktioniert es auch wieder für (n-1)-1 etc., also letztlich für alle n.

Die Schlussfolgerung nach dem letzten Komma ist falsch. Wenn dann wäre das Zufall.

chasey82 · 9 September 2009

Fratz schrieb:
Ich habe noch NIE gelesen, dass man die Aussage für n behauptet und für n-1 beweist. Das würde nämlich heißen, dass wenn ich bei n=0 anfange es für alle negativen ganzen Zahlen und 0 bewiesen wäre, nicht aber für alle natürlichen Zahlen.

Die Schlussfolgerung nach dem letzten Komma ist falsch. Wenn dann wäre das Zufall.

Haaaa da weiß ja nun ich was *GG* und das obwohl meine Klausurvorbereitung in Sachen Beweise noch gar nicht gut läuft *G

Also bei nem Induktionsbeweis wählt man zuerst ein n mit dem die Behauptung geprüft wird, also z.B. prüft man die Behauptung für n=0
Wenn das zutrifft nimmt man an das die Behauptung für n-1 und n>= 1 bewiesen sei!
So steht es in vieeeelen Beispielen zur Vollständigen Induktion 🙂 Somit kann man den Beweis auch mit n-1 machen weil n ja jedesmal um 1 erhöht wird!

Man kann das ganze natürlich auch für n+1 machen da man in der Regel für das erste n (z.B. n=0) das ganze bereits geprüft hat.

@ Fratz dann hast du noch nicht so viel im Bereich Mathe mit vollständigen Induktionen gemacht oder ?? 😛

Fratz · 9 September 2009

Einer der häufigsten Fehler beim Induktionsbeweis: Man glaubt es gelte für alle natürlichen Zahlen, tatsächlich kann es aber sein, dass eine Behauptung erst ab n=2 gilt.

Weiter: Das erste n=n0 wählt man nicht beliebig, sondern speziell!

Die Induktionsschritte n -> n+1 sind genau genommen immer einzeln durchzuführen. Man fängt bei n0 an und arbeitet sich schrittweise mit +1 vor (was etwas andere als -1 zurück ist), also n0, n0+1, n0+2. Da man das nicht für unendlich viele Zahlen machen kann gibt es den Induktionsbeweis. Dieser hat aber IMMER einen Anfang bei n0. Wenn mein n0=2 ist gilt der Beweis nun mal nur für alle n>=n0. Die Schlussfolgerung, es gelte für alle n und damit auch für n=1, muss nicht richtig sein, sondern es wäre Zufall!

Ich Frage mich immer noch, woher das n-1 herkommt. Wer schreibt das?

Edit: Habs selber gefunden. n-1 nutzt man um zum Beispiel negative n zu beweisen (das war mir jetzt auch neu). Will man Aussagen für Ganze Zahlen beweisen wählt man ein n0 und macht anschließend zwei Beweise durch vollständige Induktion, einmal mit n+1 und einmal mit n-1, nur einen Beweis durchzuführen reicht bei Ganzen Zahlen NICHT aus.

chris* · 9 September 2009

Fratz schrieb:
Ich Frage mich immer noch, woher das n-1 herkommt. Wer schreibt das?

Ich denke, damit ist eigentlich gemeint, dass man das Induktionsprinzip normalerweise so einführt, dass im Induktionsschritt von n auf n+1 geschlossen wird, während jedoch Prof. Hochstättler in 1142 es anscheinend vorzieht, von n-1 auf n zu schließen. Ich hab ja hier schon einige Fragen zum Thema Induktion beantwortet, anscheinend ist es schwierig zu verstehen, dass das auch geht.

Den Schluss von n auf n-1 hat Thorkel erstmals eingebracht, aber ich finde, seine Erklärung macht nicht den Eindruck, als hätte er das auch ernsthaft so gemeint. Die Beschreibung:

Da es hier gelingt, die n-1 Ausdruck so umzuformen, daß im Prinzip wieder der Anfangsausdruck herauskommt,

entspricht nämlich eher dem Schluss n-1 auf n.

chasey82 · 10 September 2009

Fratz schrieb:
Einer der häufigsten Fehler beim Induktionsbeweis: Man glaubt es gelte für alle natürlichen Zahlen, tatsächlich kann es aber sein, dass eine Behauptung erst ab n=2 gilt.

Ich habe geschrieben man prüft z.B. für n=0, das ist klar das dieser Wert vom eigentlichen Gültigkeitsbereich abhängt 🙂

Naja .. meine eigentlichen Probleme liegen derzeit auch noch beim Induktionsschritt. Aber mit ein bischen Übung sollte das auch noch klappen das ich da etwas Routine rein bekomme

Thorkel · 10 September 2009

chris* schrieb:
Den Schluss von n auf n-1 hat Thorkel erstmals eingebracht, aber ich finde, seine Erklärung macht nicht den Eindruck, als hätte er das auch ernsthaft so gemeint.

Hab ja nur versucht, es so zu erklären, wie ich es verstanden hab, mag ja falsch sein. Für die Induktionsaufgabe in der damaligen Klausur hats gereicht, aber vielleicht war ich da auch noch schlauer.

Und ja - in Algorithmischer Mathematik von Prof. Hochstättler werden grundsätzlich ALLE Induktionen über n-1 geführt statt n+1.

Gruß
Thomas

Fratz · 10 September 2009

chris* schrieb:
entspricht nämlich eher dem Schluss n-1 auf n.

Also wenn n-1 -> n gemacht wird habe ich gar nichts auszusetzen, weil es vom Prinzip das Gleiche ist wie n -> n+1 ist! Für mich klangen die Ausführungen oben aber nach n -> n-1, und das ist was anderes.

Vollständige Induktion - wo ist der Beweis?

Thorkel

Thorkel

Weiter lesen