Diskussion:Vollständige Induktion

Dieser Artikel war am 14. Oktober 2017 der Artikel des Tages.

Auf dieser Seite werden Abschnitte monatlich automatisch archiviert, deren jüngster Beitrag mehr als 2900 Tage zurückliegt und die mindestens einen signierten Beitrag enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleiben mindestens 5 Abschnitte.

Auf dieser Seite werden Abschnitte montags automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind und ihr jüngster signierter Beitrag mehr als 30 Tage zurückliegt. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Archiv

Archiv

Wie wird ein Archiv angelegt?

Stolperfallen mit aufnehmen ?

Hallo! Bei der vollst. Induktion gibt es ja eine Reihe von Stolperfallen in die man treten kann. Hier ein lustiges Beispiel:

Behauptung Alle Katzen haben die selbe Farbe.

Beweis:

1. In einer einelementigen Menge (n = 1) von Katzen haben alle Katzen die selbe Farbe
2. Angenommen, alle Katzen einer n-elementigen Menge haben die selbe Farbe.
3. Gegeben sei nun eine n+1-elementige Menge von Katzen. Entfernt man eine Katze A aus dieser Menge, so haben alle Katzen der Restmenge die selbe Farbe (folgt aus Indunktionsannahme). Fügt man Katze A wieder hinzu und entfernt eine andere Katze B, so haben wieder alle Katzen der Restmenge die selbe Farbe
4. Also haben A und B die selbe Farbe und damit alle Katzen der n+1-elementigen Menge

Wo liegt der Fehler? :-) Damit A und B überhaupt unterschiedliche Katzen sein können muss die Menge mindestens 2 Elemente haben. Die Behauptung müsste also für n = 2 statt für n = 1 explizit gezeigt werden, daher rührt der Fehler!

Ich glaube der Induktionsanfang ist ok. Ich hätte eher gesagt für den Spezialfall A(1)=>A(2) ist der Induktionsschritt nicht korrekt.

Sollte man an irgend einer Stelle des Artikels auf die typischen Stolperfallen hinweisen? Wenn ja, wo? Und was für Stolperfallen gibt es sonst noch? -- Prometeus 14:31, 9. Apr. 2005 (CEST)

Aus meiner Sicht spricht nichts dagegen, möglicherweise sehen aber andere das kritischer. Einbauen kann man das beispielsweise als neues Kapitel ganz am Ende (nach Verallgemeinerungen). Andere Stolperfallen sind beispielsweise solche, die für "viele" n gelten (z.B. n*n + n + 41 ist prim) oder solche, wo der Induktionsschritt klappt, aber der Anfang nicht gilt (also irgendeine Summenformel, wo man einfach eine Konstante abzieht). --NeoUrfahraner 17:46, 9. Apr. 2005 (CEST)

Hab den Spaß mal unter "Tipps zur Anwendung - Häufige Fehler" eingefügt. Ein ernsthafteres Beispiel ist mir für den 2. Fall auf die Schnelle nicht eingefallen. Andererseits bleien Kuriosa ja besser im Gedächtnis ;-)

--Prometeus 18:43, 9. Apr. 2005 (CEST)

Ist zwar schon zehn Jahre alt und längst aus dem Artikel verschwunden, aber falls sich jemand hierhin verirrt: Der Induktionsanfang n=2 ist deshalb erforderlich, weil Gleichfarbigkeit eine (mindestens) zweistellige Relation und in einer einelementigen Menge nicht definiert ist. Der Fehler liegt hier also nicht in einer falschen Anwendung des Induktionsverfahrens. (Die Begründung oben ist unzutreffend, denn A und B werden aus der n+1-elementigen Menge genommen, und die hat durchaus mindestens zwei Elemente.) -- 87.145.237.75 00:38, 7. Sep. 2015 (CEST)

Löschung des Abschnitts "Konstruktive Benutzung der vollständigen Induktion"

Ich habe diesen Abschnitt ersatzlos gelöscht. Es handelt sich keineswegs um eine 'konstruktive' Benutzung eines Beweisverfahrens, derart, dass eine wahre Aussage sozusagen 'errechnet' wird.

Ich habe wirklich wunder was gedacht und deshalb den genannten Artikel aus den Semesterberichten im Zeitschriftenmagazin aufgesucht und gelesen. Es wird dem Autor dieses Artikels sicher nicht recht sein, hier noch Jahrzehnte später so prominent an ziemlich unpassender Stelle erwähnt zu werden, zumal die Idee nicht einmal von ihm ist (wie im Artikel selbst angemerkt). Der Autor benutzt lediglich das Verfahren der vollständiger Induktion quasi in retrograder Weise (und genau genommen, selbst das nicht), um eine Aussageform A(k) geschickt zu erraten(!), die dann hoffentlich mit ('vorwärts' durchgeführter) vollständiger Induktion für alle natürlichen Zahlen bewiesen werden kann. Das Ganze gehört in den Bereich 'systematisches Raten', wie es wohl die meisten Theoretiker in ihren Arbeitsstuben machen, und ist in keinem Fall etwas 'Konstruktives'. --Stefan Neumeier (Diskussion) 20:06, 10. Feb. 2015 (CET)

Einleitung mit verwirrten Begriffen

In der Einleitung stand

»Die verallgemeinerte Formulierung der Aussage für eine variable natürliche Zahl n und die nächstfolgende, nämlich n+1 wird auch als Induktionsvoraussetzung bezeichnet.«,

was nicht stimmt. [Wie auch weiter unten im Artikel durchaus zu finden, sind n und n+1 nicht gleichrangig, sondern Aussage(n) ist die Induktionsvoraussetzung, aus der durch logisches Schließen (den Induktionsschritt) die Aussage(n+1) zu gewinnen ist.] Das konnte nicht so stehen bleiben, auch nicht in der Einleitung. Gleichzeitig habe ich die Namen der Aussagen durch aufrechtes \operatorname{} gekennzeichnet. --Nomen4Omen (Diskussion) 18:35, 22. Aug. 2018 (CEST)

Die Einleitung ist total verkorkst

Was soll denn das? "In den Lehrbüchern sind zwei Schrittten ...". Wenn das ein Schüler oder angehender Student liest, kann er damit nichts anfangen. Macht es doch nicht so kompliziert!

Ich bin dafür, die "alte" Version wieder herzustellen. Die lautet:

"Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird, die größer oder gleich einem bestimmten Startwert sind. Da es sich um unendlich viele Zahlen handelt, kann solch ein Beweis nicht für alle Einzelfälle durchgeführt werden.

Der Beweis wird daher in zwei Etappen durchgeführt: als Induktionsanfang für eine kleinste Zahl, für die man die Aussage zeigen will (meist 1 oder 0), und als Induktionsschritt, der aus der Aussage für eine variable Zahl die entsprechende Aussage für die nächste Zahl logisch ableitet.

Dieses Beweisverfahren ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik."

--Joachim Mohr (Diskussion) 15:49, 23. Aug. 2018 (CEST)

Die neue Version habe ich noch abgeändert in

"Der Beweis, dass die Aussage $\operatorname {A} (n)$ für alle $n\geq n_{0}$ ($n_{0}$ meist 1 oder 0) gilt, wird daher in zwei Etappen durchgeführt:

1. Im Induktionsanfang wird die Aussage $\operatorname {A} (n_{0})$ für eine kleinste Zahl $n_{0}$ hergeleitet.
2. Im Induktionsschritt wird die Aussage $\operatorname {A} (n+1)$ aus der Aussage $\operatorname {A} (n)$ für $n\geq n_{0}$ hergeleitet."

Dass der Induktionaschritt zu ...

Im Induktionsschritt wird die Aussage für eine beliebige (natürliche) Zahl hergeleitet – basierend auf der Annahme, dass die Aussage für alle vorausgehenden Zahlen ... zutrifft.

...könnte man in einem Unterabschnitt erwähnen. --Joachim Mohr (Diskussion) 16:19, 26. Aug. 2018 (CEST)

Im Übrigen

Siehe oben: Duden-Schülerhilfe-Aufbau des Zahlensystems, vollständige Induktion

  1. Induktionsanfang
  2. Induktionsschluss
  2a. Induktionsvoraussetzung
  2b. Induktionsbehauptung
  2c. Induktionsschritt

Siehe: Mathematik, Lehrbuch für Klasse 11, 4. Auflage, Volk und Wissen, Volkseigener Verlag Berlin.- 1985, S. 32-33

 1. Induktionsanfang
 2. Induktionsschritt
 2a. Induktionsvoraussetzung
 2b. Induktionsbehauptung
 2c. Induktionsbeweis

Schlussfolgerung: Abgesehen von den Begriffen sind die Gliederungspunkte doch inhaltlich gleichrangig?! Dann kürzer so:

 1. Anfang
 2. Behauptung
 3. Voraussetzung
 4. Beweis

Das Wort Induktion wird ja schon von der Überschrift "Vollständige Induktion" geliefert. --Walmei (Diskussion) 12:45, 28. Aug. 2018 (CEST)

Aussageformen

Mein Einwurf zu den vorangegangenen Diskussionen:

Das Problem bei der vollständigen Induktion ist, dass der Begriff Aussage nicht präzise genug ist.

Eigentlich handelt es sich um Aussageformen und ob diese allgemeingütltig sind.

Und dann handelt es sich um logische Schritte, die vorher eingeübt werden sollten. Die Schwierigkeit für Schüler und Studenten bei der vollständigen Induktion ist, dass diese Übungen vorher nicht eingeübt wurden.

Kleine Vorübung:

Sind die folgenden Aussageformen in N allgemeingültig?

a) Wenn n ein Vielfaches von 6 ist, dann ist n eine gerade Zahl.
b) Wenn n = 0 ist, dann ist n + 1 = 1.
c) Wenn n = n + 1 ist, dann ist n + 1 = n + 2. 

Entnommen von https://kilchb.de/vollstind.php

Die Aufsplitterung

  1. Induktionsanfang
  2. Induktionsschluss
  2a. Induktionsvoraussetzung
  2b. Induktionsbehauptung
  2c. Induktionsschritt

ist nur ein pädagogischer Hilfsschritt.

Beim Induktionbeweis muss man der Induktionsanfang und als zweiter Schritt die wenn-dann-Aussage A(n) => A(n+1) nachgewiesen werden. Dabei wird zunächst A(n) (Induktionsvoraussetzung) formuliert, dann gesagt dass A(n+1) (Induktionsbehauptung) gezeigt werden muss und schließlich, wie das bewerkstelligt wird (Induktionsschritt). Aber das sind pädagogische Hifsmittel, die mit dem Begriff Vollständige Induktion nichts zu tun haben.

--Joachim Mohr (Diskussion) 17:53, 28. Aug. 2018 (CEST)

Warum reicht der Induktionsanfang aus?

Man setzt n=1 ein, erhält eine wahre Aussage und nutzt dies dann, um die gesamte zu beweisende Formel für n+1 zu bewiesen, indem man geschickt klammert und so umformt, dass man den n-Term (ohne +1) wieder durch die ursprügnlcihe n-Formel (ohne+1) zurückeinsetzen kann, damit wieder eine wahre Aussage rauskommt -> q.e.d.

Warum geht das? Damit nehme ich doch bereis implizit an, dass es halt doch schon für alle n gilt, obwohl ich es nur für ein einziges willkürlich gewähltes n gezeigt habe. Ich stecke das zu Beweisende also doch schon als wahr angenommen rein und komme dann natürlich als Zirkelschluss wieder korrekt raus. Ein echter Beweis wäre es doch nur, wenn ich den sogenannten Induktionsanfang gar nicht benutzen würde, es also wirklich für alle n zeigte.

Das Zurückeinsetzen der kompletten n-Gleichung in die geschickt umgestellte n+1-Gleichung darf ich doch eigentlich nicht machen, da diese n-Gleichung noch gar nicht beweisen ist (genau die will ich ja gerade erst beweisen). Ich darf doch eigentlich nur mein n0 (den Anfang) einsetzen, denn nur für diese einzige Zahl weiß ich ja, dass es gilt.

Also, warum geht das? --2003:DE:F14:5700:B4FA:5AED:D684:4E57 22:03, 30. Dez. 2021 (CET)

Die vollständige Induktion in der Form

I Induktionsanfang: Prüfe, ob A(1) gilt.

II Induktionsschritt: Zeige: A(n) => A(n+1) (n ε N)

("Aus A(n) kann A(n+1) hergeleitet werden")

setzt eine gute Kenntnis der Aussagelogik voraus.

Vielleicht hilft Dir Crashkurs der vollständigen Induktion weiter. --Joachim Mohr (Diskussion) 10:44, 2. Jan. 2022 (CET)

Joachim Mohr hat vollkommen recht. Und der Induktionsanfang (I) reicht NICHT aus! Sei $n_{0}$ die erste Zahl, für die wir's beweisen können oder wollen, und sei deshalb ${\mathsf {A}}(n_{0})$ wahr.

Meistens ist der sog. Induktionsschritt (II) schwieriger, auf jeden Fall seine Formulierung: Wir setzen voraus die Kenntnis der natürlichen Zahlen $\mathbb {N}$ und nehmen an,

1. $n\geq n_{0}$ ist irgend eine solche (also $n_{0}\leq n\in \mathbb {N}$) und nehmen an, dass (das ist noch nicht bewiesen und das obige "... halt doch schon für alle n gilt" ist total fehl am Platz, obwohl es nachher so rauskommt ! Wir tun so, als ob)
2. die Aussage ${\mathsf {A}}(n)$ wahr ist.

(Jetzt kommt der ausführlich ausgesprochene Induktionsschritt:) Wenn wir aus diesen zwei Annahmen die Aussage ${\mathsf {A}}(n+1)$ beweisen können, wenn also

${\bigl (}(n_{0}\leq n\in \mathbb {N} )\;\land \;{\mathsf {A}}(n){\bigr )}\quad \Longrightarrow \quad {\mathsf {A}}(n+1)$

als Implikation zutrifft, dann gilt ${\mathsf {A}}(n)$ für alle $n\geq n_{0}\land n\in \mathbb {N}$. –Nomen4Omen (Diskussion) 16:51, 2. Jan. 2022 (CET)

Einleitung

Ist es wirklich sinnvoll in der Einleitung n und n-1 zu verwenden (Schluss von n-1 auf n), wenn anschließend bei praktischen allen Beispielen und weiteren Beschreibungen immer der Schluss von n auf n+1 verwandt wird (mal ganz zu schweigen von der Darstellung in der Referenzliteratur). Natürlich das mathematisch letztlich egal, aber einer Konsistenz in der formalen Darstellung in Einleitung und Haupttext wäre mMn. schon wünschenswert bzw. zu bevorzugen.--Kmhkmh (Diskussion) 17:15, 2. Jan. 2022 (CET)

Ich stimme dir 100%-ig zu: Schluss von n-1 auf n ist leicht irrig, weil n-1 keine freie Variable ist und hier eine solche gebraucht wird. –Nomen4Omen (Diskussion) 17:38, 2. Jan. 2022 (CET)

✅ Habe es umgeformt! --Joachim Mohr (Diskussion) 09:31, 3. Jan. 2022 (CET)

Induktion als Schlussregel

Hallo,

im Artikel findet sich der folgende Formel: "$A(n_{0})$ und $\forall n\in \mathbb {N} \colon (n\geq n_{0}\land \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1))\ \vdash \ \forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n))$". Ich fürchte, dass das "$A(n_{0})$ und $\forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1))\ \vdash \ \forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n))$" heißen muss. Oder irre ich mich? Was sagt ihr?

Verbesserung: Da soll natürlich $n\geq n_{0}\Rightarrow (A(n)\Rightarrow A(n+1))$ stehen.

--Anthroporraistes (Diskussion) 18:58, 6. Feb. 2022 (CET)

Ich habe Folgendes verstanden:

Alt:

$A(n_{0})$ und $\forall n\in \mathbb {N} \colon (n\geq n_{0}\land \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1))\ \vdash \ \forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n))$.

Ich fürchte, dass das neu:

$A(n_{0})$ und $\forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1))\ \vdash \ \forall n\in \mathbb {N} \colon (n\geq n_{0}\Rightarrow \operatorname {A} (n))$

heißen muss.

Also das Letztere kann nicht sein, weil die Kette $n\geq n_{0}\Rightarrow \operatorname {A} (n)\Rightarrow \operatorname {A} (n+1)$, die in deiner Formel steckt, völlig fehl am Platz ist. –Nomen4Omen (Diskussion) 20:37, 6. Feb. 2022 (CET)

Sorry, da müssen natürlich Klammern stehen. Ich meine <math> n\geq n_0 \Rightarrow (A(n)\Rightarrow A(n+1)) </math>. --Anthroporraistes (Diskussion) 23:56, 6. Feb. 2022 (CET)

Begründung für Löschung eines Erklärvideos

Erst ab Minute 8 stimmen die Video-Erläuterungen mit Wikipedia überein. Der Moderator verwendet den Begriff "Induktionshypothese", das ist für den Anfänger verwirrend. Man sollte bei den ersten Übungen auf das Summenzeichen Sigma verzichten und stattdessen die Summenglieder einzeln angeben, dann sieht man besser, welche Partialsumme durch die Induktionsvoraussetzung ersetzt wurde. (nicht signierter Beitrag von Klaus31415 (Diskussion | Beiträge) 18:03, 25. Apr. 2022 (CEST))