Diskussion:Vollständige Induktion

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Inhaltsverzeichnis

1 Häufige Fehler
2 Was ist eine "unvollständige" Induktion?
3 Was ist den nun die korrekte Form?
4 Bedingungen genauer mit Beispiel erklären
5 strukturelle Induktion
6 Verallgemeinerungen
7 Stolperfallen mit aufnemhen ?
8 ad Die Idee
9 Unlogisch...?
10 Unlogisch 2 aka zuwenig Zeilenabstand
11 Lesenswert-Diskussion
12 "Man beruft sich auf den Fall n=2 ??"
13 Geschichtlich: frühere Verwendung der Induktion?
14 Ist das Induktionsprinzip deduktiv?
15 Induktive vs. Rekursive Definition

[Bearbeiten] Häufige Fehler

Bei "Häufige Fehler" wird eine schöne Formel gezeigt. Durch mein "Vorwissen" habe ich in der rechten Formel "+7" erkannt.

Zitat: Falls diese Behauptung für ein n gelten würde, dann würde sie auch für n + 1 gelten! Da sie aber für kein n gilt, ist sie falsch! Zitat-Ende

Und woher WEIß ich das, das sie für kein n gilt?

Danke für die Erklärung. LG Lisa

Ich habe es ein wenig umformuliert. Der Induktionsbeweis ist falsch, wenn man kein n für den Induktionsanfang angibt. Die Aussage könnte trotzdem richtig sein, auch wenn der Beweis falsch ist. Dass die Aussage im konkreten Fall tatsächlich falsch ist, muss man aber tatsächlich mit anderen Mitteln zeigen (beispielsweise indem man die korrekte Formel angibt und zeigt, dass sie niemals gleich der angegebenen falschen Formel ist). --NeoUrfahraner 21:46, 2. Sep 2006 (CEST)

[Bearbeiten] Was ist eine "unvollständige" Induktion?

Habe das bisher noch nicht gehört und kann mir nichts darunter vorstellen. Was wäre dann der Unterschied einer unvollständigen Induktion und einer vollständigen Induktion?

Wo steht denn was von "unvollständiger" Induktion? --NeoUrfahraner 22:41, 23. Aug 2006 (CEST)

Habe ich auch schon gehört, aber verstehe es nicht. LG Lisa

Hilft http://www.phillex.de/u-indukt.htm weiter? --NeoUrfahraner 21:50, 2. Sep 2006 (CEST)

[Bearbeiten] Was ist den nun die korrekte Form?

Hier wird angegeben:

  1. Induktionsanfang
  2. Induktionsvoraussetzung
  3. Induktionsschritt

In der Schule habe ich:

  1. Induktionsanfang
  2. Induktionsvoraussetzung
  3. Induktionsschluss

Im Duden-Schülerhilfe-Aufbau des Zahlensystems, vollständige Induktion finde ich:

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

Der Beginn heißt normalerweise Induktionsverankerung, weil am ersten Schritt die ganze Sache wie an einem Anker hängt. Den Begriff der Induktionsvoraussetzung kenne ich nicht, wundert mich auch, da es keine Voraussetzung sondern eine Annahme ist. Wenn ich annehme, dass die Sache für n gilt, gilt sie dann auch für n+1? Voraussetzungen können wahr oder falsch sein, Annahmen werden als wahr unterstellt, mit dem Ziel den Wahrheitsgehalt später im Beweisverfahren zu verifizieren oder zu falsifizieren.

--Dompfaf 22:14, 6. Jun 2006 (CEST)

"Verankerung" klingt für mich nach Kuschelpädagogik.--Gunther 22:19, 6. Jun 2006 (CEST)

--Soviel dazu, das Mathe eindeutig ist, nun gibt es schon vier verschiedene Bezeichnungen für das Selbe. *kopfschüttel* --Warum muss jeder sein eigenes Brötchen backen bzw. das Rad neuerfinden??? *verwundertschau*

--Ich schlage vor, Bezeichnungen ähnlich derer aus dem Duden-Schülerhilfe zu verwenden. Die Voraussetzung/Behauptung (Hier sehe ich keinen Unterschied, sodass meiner Meinung nach einer von beiden Punkten ausreicht. Ich empfehle "Voraussetzung", da die Aussage (für ein gewisses n) mit dem Induktionsanfang schon bewiesen ist.) macht als eigenständigen Punkt keinen Sinn. Erst zusammen mit dem Schritt/Schluss erhält er Bedeutung. Da die Begriffe I-Schritt und I-Schluss häufig das selbe meinen, denke ich, man sollte nur einen angeben oder beide synonym verwenden. Etwa so:

  1. Induktionsanfang
  2. a) Induktionsvoraussetzung
     b) Induktionsschluss/-schritt

Zumindest besser als die aktulle Bezeichnung ist die Duden-Version ohne Schritt 2b.

[Bearbeiten] Bedingungen genauer mit Beispiel erklären

Hallo, ist es möglich, die Bedingungen der VI genauer zu erklären? Hier sollte man den genauen Unterschied einer "mangelhaften" Induktion und der vollständigen Induktion erkennen. In dem Bereich werden auch viele Denkfehler gemacht. Ich zum Beispiel. Danke, LG Kirsten.

Ich denke ein einfaches Beispiel wie z.B. die Summe der natürlichen Zahlen von 1 bis n sollte genügen. Die Summe der ungeraden Zahlen als weiteres Beispiel trägt nach meiner Meinung wenig zum Verständnis bei. Es fragt sich was mit diesem Beispiel eigentlich ausgesagt werden sollte. Der Beweis durch Induktion erscheint mir in diesem Fall nicht besonders elegant. Ich würde in diesem Beispiel die Berechnung unter Verwendung der Formel für die Summe der Zahlen 1 bis N vorziehen. Auch die Summenformel für die ersten N natürlichen Zahlen lässt sich auch einfach ohne Verwendung der vollständigen Induktion beweisen. Die Summe der Zahlen von 1 bis 100 ist (1+100) + (2+99) + ... + (50+49) = 51*50 = N*(N+1)/2. Bei einer geraden Zahl an Summanden kann entsprechendend dieses Prinzips immer die größste und die kleinste Zahl zusammengefasst werden. Bei einer ungeraden Anzahl kann die Null als weiterer Summand aufgenommen werden. Die Induktion ist also meist nicht die einzig möglich Beweismethode.

Die Gaußsche Herleitung ist sicher intuitiv, aber ist sie auch mathematisch rigoros als Beweis zu verstehen, oder muß ihre allgemeine Gültigkeit nicht selber (durch Induktion!) bewiesen werden?

Die jetzt gemachte Ergänzung erläutert zwar, warum es funktioniert, ist aber kein Nachweis, dass es sich um einen mathematisch rigorosen Beweis handelt (sprich, um eine Argumentationskette, die nur (möglicherweise indirekt) auf den Axiomen der natürlichen Zahlen beruht).

Genauer: Für jeden einzelnen Fall ist es unmittelbar einsichtig, daß diese Umordnung der Summanden durchgeführt werden kann und dieses Ergebnis liefert. Aber kann man die allgemeine Aussage (diese Umordnung zu konstanten Summanden ist für jedes n möglich) auch streng mathematisch ohne Induktion beweisen? --Ce 19:04, 30. Nov 2003 (CET)

Ich denke, diese Umordnung ist kein mathematisch strenger Beweis. Die Begründung des Satzes durch die Umordnung ist ein Fall von Induktion im logischen Sinne, d.h. der Schluss vom speziellen aufs allgemeine. Innerhalb unserer Mathematik ist das aber kein Beweis. Ein Beweisverfahren ist dagegen die deduktive (!) Methode der vollständigen Induktion (auf diese Namensverwirrung sollte man vllt. auch mal eingehen).

In diesem Sinne wäre also ein Nachweis, dass die Umordnung stets möglich ist, wiederum nur durch vollständige Induktion möglich. --SirJective 19:17, 30. Nov 2003 (CET)

Also, die Frage ist hier letztlich, wo man die Trennlinie zu dem zieht, was man als bekannt voraussetzen darf. Es geht bei 1 + ... + n nicht um eine Reihensumme mit unendlich vielen Gliedern, wo das Umordnen von Gliedern in der Tat mit Vorsicht angegangen werden müßte. Daß man hingegen endlich viele Summanden der Zahlenreihe 1 + ... + n ohne Änderung des Ergebnisses beliebig umordnen und zusammenfassen kann, egal, welchen konkreten Wert n gerade hat, ergibt sich aus den Axiomen der Addition (Kommutativität und Assoziativität). Diese sind zwar nur für zwei bzw. drei Summanden formuliert. Ich meine, daß es fast schon komisch ist, hier die beliebige Vertauschbarkeit und Zusammenfaßbarkeit von endlich vielen Summanden in der Form eines exakten Beweises aufzuschreiben, obwohl dies möglich ist. Ich meine, wer Spaß daran hat, kann es für sich einmal beweisen und dabei vollständige Induktion anwenden. Da die Axiome für die natürlichen Zahlen eigentlich nur so praktische Erfahrungen wie die beliebige Vertauschbarkeit und Zusammenfaßbarkeit von endlich vielen Summanden in eine einfache Form bringen sollen, würde man an der Stelle genau genommen nur beweisen, daß die Axiome eine gelungene Vereinfachung der Beschreibung dessen sind, was man nur beobachten, aber nicht beweisen kann. Zusammengefaßt meine ich also, daß man Gauß' Herleitung der Summenformel für die natürlichen Zahlen bis 100 analog als strengen gültigen Beweis für die Summe bis n ohne vollständige Induktion akzeptieren kann und muß. Die beliebige Kommutativität und Assoziativität von endlich vielen Summanden wird bei diesem Beweis meiner Meinung nach zu recht vorausgesetzt. Ich stimme zu, daß ein Beweis, der für eine konkrete Zahl (hier: 100) erbracht wurde, nicht ohne weiteres auf beliebige Zahlen n verallgemeinert werden kann. In diesem Fall ist es aber so, daß die allgemeine Betrachtung für n genauso wie für die konkrete Zahl 100 angestellt werden kann, da es sich bei n immer um eine endlich große Zahl handelt. Da der Beweis so für ein allgemeines n geführt werden kann, gilt er auch für jedes n. - 212.202.53.9 - 05.12.2003

Die Gausssche Begruendung ist eine schoene, einfache und gut verstaendliche. Jedoch sehe ich gerade nicht, wie z.B. die Aussage "Die Summe der Zahlenpaare wird zu n+1 und die Anzahl der Zahlenpaare [wird] zu n/2" rein logisch gefolgert werden koennte. Dies ist mMn jedoch noetig, um von einem mathematischen Beweis sprechen zu koennen. Denn der hat bitteschoen innerhalb des Axiomensystems zu bleiben. Die Vertauschbarkeit endlich vieler Summanden kann man selbstverstaendlich als bekannt voraussetzen, da liegt auch nicht mein Problem. Mir bereitet die Stelle Kopfzerbrechen, an der auf die Summe und die Anzahl der Zahlenpaare geschlossen wird, nicht die Existenz der Umordnung und Gleichwertigkeit zur urspruenglichen Reihenfolge. Da hab ich den Satz im Artikel wohl falsch geschrieben:

...wenn sichergestellt ist, dass die beschriebene Umordnung der Zahlen und Addition der Paare für jede natürliche Zahl n möglich ist und das angegebene Ergebnis liefert

Die Umordnung und Addition ist natuerlich moeglich, fraglich ist nur, warum das angegebene Ergebnis herauskommt. --SirJective 10:29, 5. Dez 2003 (CET)

Der Satz soll doch nur ein (etwas langatmiges) Beispiel für die Beweistechnik der vollständigen Induktion sein. Daher gehört die nette Geschichte vom kleinen Gauss IMHO nicht in diesen Artikel. Der axiomatische Aufbau des Zahlensystems wurde ja erst später entwickelt. Heizer 23:04, 5. Dez 2003 (CET)

Gauss hat die Summanden keineswegs umgeordnet. Seine Idee: Er hat die Summe 2 mal untereinander geschrieben, zuerst vorwärts, dann rückwärts. Danach hat er die beiden Zeilen spaltenweise addiert:

s(n)      =   1   +   2   + ... + (n-1) +  n         vorwärts
s(n)      =   n   + (n-1) + ... +   2   +  1         rückwärts
-----------------------------------------------
s(n)+s(n) = (n+1) + (n+1) + ... + (n+1) + (n+1)      Addition

Daraus ergibt sich sofort 2·s(n) = n (n+1) und daraus dann die Summenformel.
Das ist in dem Artikel m.E. etwas unglücklich dargestellt. -- tsor 23:41, 5. Dez 2003 (CET)

Sehr schön. Auf diese Weise ist das Verfahren viel klarer.

Es ist auch klarer zu sehen, an welcher Stelle es "haken" könnte:

Wie beweist man ohne Induktion, dass in der unteren Summe unabhängig von n alle Summanden gleich (n+1) sind? --Ce 19:59, 6. Dez 2003 (CET)

Es handelt sich jeweils um endlich viele Summanden, und es gibt eine eineindeutige Zuordnung zwischen den Summanden der oberen und der unteren Reihe.

Der i-te Summand der oberen Reihe ist i; der i-te Summand der unteren Reihe ist (n+1)-i. Dies folgt direkt aus der Aufgabenstellung und aus der zulässigen beliebigen Umordnung endlich vieler Summanden aus den natürlichen Zahlen (das Rückwärtsaufschreiben der Summe ist ja auch eine Umordnung). Die Summe ist jeweils i + (n+1)-i = n+1.

Dies ist nicht mehr und nicht weniger einsichtig, als die Beweiskraft des Verfahrens der vollständigen Induktion.

Meines Erachtens ist es nicht so, dass durch die Aufstellung der Axiome für die natürlichen Zahlen und durch die Konzeption des Beweisverfahrens der vollständigen Induktion andere Beweisverfahren nicht mehr gültig sind, die auf den gleichen Grundlagen beruhen (Eigenschaften der natürlichen Zahlen), nur weil sie nicht genau dem Algorithmus dieser Methode entsprechen. Hier muss man wohl grundsätzlich darauf achten, dass Fortschritte in den Methoden und bei den Begriffsbildungen nicht zu einer Verengung der Sicht und Vereinnahmung dessen führen, was vorher schon richtig und gültig war. Die Anekdote mit Gauß kam in den Beitrag, weil in einer vorhergehenden Version behauptet worden war, die Summenformel für 1 + .... + n könne ohne vollständige Induktion nicht bewiesen werden. Dies ist sicherlich falsch. 07.12.2003 (212.202.52.146)

Um es klar zu sagen: Man kann die Summenformel auf (mindestens) 2 Arten beweisen: Einmal mit der "direkten" Methode , so wie es Gauss tat. Andrerseits kann man die Formel auch mit dem Verfahren der vollständigen Induktion beweisen. Beide Beweise sind gültig und gleichwertig.
Um die Gauss-Methode noch ein wenig zu präzisieren: Man wählt zunächst eine beliebiges n > 0 und hält dieses dann fest. Für dieses feste n führt man obigen Beweis (Summe vorwärts und rückwarts schreiben und dann addieren) durch. Und weil n beliebig gewählt wurde gilt der Beweis für alle n > 0. -- tsor 16:43, 7. Dez 2003 (CET)

Der Artikel handelt nicht von den verschiedenen Beweismöglichkeiten der Summenformel, sondern von der vollständigen Induktion.
unstrittig -- tsor 22:21, 10. Dez 2003 (CET)
Nach heutigen Massstäben muss ein mathematischer Beweis formalisierbar sein. Natürlich gab und gibt man sich oft damit zufrieden, ihn plausibel zu machen. Was man dazu "braucht", ist eine didaktische, soziologische und psychologische Frage (meist genügt die Autorität des Mathe-Lehrers ;-)).
???? -- tsor 22:21, 10. Dez 2003 (CET)
Im modernen axiomatischen Aufbau des Zahlensystems (das auf Sparsamkeit der Axiome ausgelegt ist) braucht (im Sinne eines formalen Beweises) man bereits für den Beweis der Kommutativität der Addition die vollständige Induktion (siehe [1]), und also auch für beide Beweise der Summenformel. Selbst bei einem anderen axiomatischen Aufbau kann man den induktiv definierten Summenausdruck nur mittels vollständiger Induktion allquantifizieren. Heizer 12:51, 10. Dez 2003 (CET)
Was bedeutet das in diesem Zusammenhang? Die Kommutativität der Addition kann man als bewiesen voraussetzen wenn man schon bei Folgen angelangt ist. -- tsor 22:21, 10. Dez 2003 (CET)

Ich würde sagen, die Schlussregeln, die man benötigt, um von den Axiomen zur Konklusio zu kommen, sind Bestandteil des Beweises. Aber lassen wir das mal beiseite. Was genau ist Dir denn unklar? Formalisierbarkeit? Allquantor oder Induktive Definition? Heizer 01:46, 11. Dez 2003 (CET)

Nobel geht die Welt zugrunde. 10.12.2003 (212.202.185.99)
ja. -- tsor 22:21, 10. Dez 2003 (CET)

Nein, das wird ein Heulen und Zähneklappern! Heizer 01:46, 11. Dez 2003 (CET)

Hallo SirJective,

Ich muß sagen, für so eine "Induktion" habe ich in einer Klausur schon 0 Punkte bekommen.

Ich mache sie mal neu (und ausführlicher).

arbol01 19:15, 10. März 2004

Deine Ergänzung sieht auf den ersten Blick sinnvoll aus, leider gibt es nun eine Doppelung in dem Abschnitt. Wenn mir keiner zuvorkommt, werde ich diese in den nächsten Tagen auflösen. --SirJective 22:04, 10. Mär 2004 (CET)

Ich muß sagen, daß es mir sehr schwer fällt, meine Ergänzung einzusetzen. Ausserdem habe ich die Induktion auf eine andere Formel angewendet.

Hier noch mal die andere vollständige Induktion:

Angewandt auf obiges Beispiel sieht das so aus:

Wir wollen eine Formel finden die die Summe aller ungeraden Zahlen von 1 bis n vereinfacht und, was wichtiger ist, wir wollen diese Formel beweisen:

1 = 1 ; 1 + 2 = 3 ; 1 + 2 + 3 = 6 ; 1 + 2 + 3 + 4 = 10

Vermutung: Die Summe aller natürlichen Zahlen von 1 bis n ergibt:

$\sum^n_{i=1} i = \frac{n*(n+1)}{2}$

Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:

$\sum^n_{i=1} i + (n+1) = \sum^{n+1}_{i=1} i$

$\sum^n_{i=1} i + (n+1) = \frac{n*(n+1)}{2} + (n+1)$

$\sum^{n+1}_{i=1} i = \frac{(n+1)*(n+2)}{2}$

$\frac{n*(n+1)}{2} + n+1 = \frac{(n+1)*(n+2)}{2}$ /* Die Perle */

Das letzte ist die Perle, die jetzt bewiesen werden muß. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.

$\frac{n*(n+1)}{2} + n+1 = \frac{(n+1)*(n+2)}{2}$

$\frac{n*(n+1)}{2} + \frac{2n+2}{2} = \frac{(n+1)*(n+2)}{2}$

$\frac{n*(n+1) + 2n + 2}{2} = \frac{(n+1)*(n+2)}{2}$

$\frac{n^2 + n + 2n + 2}{2} = \frac{n^2 + 3n + 2}{2}$

$\frac{n^2 + 3n + 2}{2} = \frac{n^2 + 3n + 2}{2}$

Damit ist die vollständige Induktion für $\sum^n_{i=1} i = \frac{n(n+1)}{2}$ abgeschlossen und bewiesen.

Ich werde das Ganze auch noch mal mit n über k und 0.9p = 1 machen.

arbol01 23:22, 10. März 2004

[Bearbeiten] strukturelle Induktion

Im Abschnitt "Verallgemeinerungen" sollte noch ein Link zur strukturellen Induktion gesetzt werden, leider bin ich mir nicht ganz sicher, wie sich diese zur transfiniten Induktion verhält, jemand mit mehr Ahnung vielleicht...? --Esperantisto 11:47, 28. Sep 2004 (CEST)

Ich kenne keine Details, aber so wie ich strukturelle Induktion verstehe, geht es dort nicht wie bei den natürlichen Zahlen um eine totale, sodern um eine allgemeinere Halbordnung; es sind also nicht wie bei den natürlichen Zahlen zwei Elemente direkt vergleichbar. Im Gegensatz zur transfiniten Induktion werden aber bei struktureller Induktion nur höchstens abzählbar viele Elemente betrachtet; insbesondere wird das Auswahlaxiom nicht benötigt. Vielleicht kann noch jemand mehr Information dazu geben.

[Bearbeiten] Verallgemeinerungen

Kann jemand einige schöne Beispiele zu den Verallgemeinerungen beitragen? So, wie es jetzt steht, wirkt es noch zu theoretisch. --NeoUrfahraner 05:16, 27. Feb 2005 (CET)

[Bearbeiten] Stolperfallen mit aufnemhen ?

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:

In einer einelementigen Menge (n = 1) von Katzen haben alle Katzen die selbe Farbe
Angenommen, alle Katzen einer n-elementigen Menge haben die selbe Farbe.
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
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!

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)

[Bearbeiten] ad Die Idee

Ich habe mir erlaubt die Einleitung dieses Abschnitts wiederherzustellen, da die ursprüngliche Textqualität weitaus besser ist und eine einfache, gut strukturierte Sichtweise bietet. Ich bitte weiters zu berücksichtigen, dass WP kein Lehrbuch ist und eine vereinfachte Textwahl auch zu Qualitätabstichen führen kann. Grüße Tom1200 12:15, 10. Jul 2005 (CEST)

Wer hat die qualität abgestochen, Tom1200? ;)) --212.100.47.161 02:19, 14. Okt 2005 (CEST)

[Bearbeiten] Unlogisch...?

Kann mir mal jemand sagen wieso laut artikel $(k+1) \cdot \frac{k+2}{2}$ gleich $\frac{(k+1)\cdot ((k+1)+1)}{2}$ ist??

Ich meine wenn man davon ausgeht dass $k + 2 = ((k + 1) + 1)$ ist, dann erscheint mit das heraufheben von $(k + 1)$ auf den bruch durch 2 doch als ungültig da $(k + 1)$ nicht gleich $\frac{(k+1)}{2}$ ist. Oder?

-- Hurricane (212.100.47.161 02:30, 14. Okt 2005 (CEST))

$\frac{(k+2)}{2}$ = $\frac{(k+1)+1}{2}$ , multipliziere beide Seiten mit $k + 1$ , dann steht genau das Gewünschte dort. Wo ist das Problem? --NeoUrfahraner 06:10, 14. Okt 2005 (CEST)

Das Heraufheben auf den Bruch ist völlig korrekt. Beispiel: $5\cdot\frac 62=5\cdot 3=15=\frac{30}2=\frac{5\cdot 6}2$ .--Gunther 09:40, 14. Okt 2005 (CEST)

[Bearbeiten] Unlogisch 2 aka zuwenig Zeilenabstand

wahrscheinlich hab ich irgendwo einen denkfehler gemacht, aber wie kommt dieser Ausdruck zustande ??

$= (k+1) \cdot \left(\frac{k}{2}+1 \right)$

wenn ich

$1 + 2 + 3 + \dots + k + (k+1)$

nach

$1+2+...+n = \frac{n(n+1)}{2}$

anwende kommt bei mir

$1 + 2 + 3 + \dots + k + (k+1) = \frac {(k+1)(k+1+1)}{2}$ raus

--Sam vimes 15:04, 9. Dez 2005 (CET)

Ja, und

$\frac{(k+1)(k+2)}2=(k+1)\cdot\frac{k+2}2=(k+1)\cdot\Big(\frac k2+1\Big).$

--Gunther 12:49, 9. Dez 2005 (CET)

Ich hatte Probleme mit

$= (k+1) \cdot \frac{k+2}{2}$

$= \frac{(k+1) \cdot (k+2)}{2}$

$= \frac{(k+1)\cdot ((k+1)+1)}{2}$

weil ich beim lesen der zeilen fälschlicherweise den Divisor der oberen Zeile zusätlich noch als Exponent gelesen habe... mein fehler

--Sam vimes 15:04, 9. Dez 2005 (CET)

[Bearbeiten] Lesenswert-Diskussion

Vollständige Induktion oder der "Schluss von n auf n + 1" ist eine Beweismethode, die üblicherweise eine Aussage für alle natürlichen Zahlen beweist. Sie funktioniert aber auch für allgemeinere Fälle (siehe unten).

Pro Antifaschist 666 16:41, 10. Okt 2005 (CEST)

Pro Gefällt mir sehr gut. Am Anfang wird ein einigermaßen allgemeinverständlicher Einstieg geboten, trotzdem ist der Artikel mathematisch fundiert. -- mkill - ノート 12:05, 12. Okt 2005 (CEST)

Momentan wirkt der Artikel auf mich noch ein wenig durcheinander (was die Gliederung angeht) und an manchen Stellen noch etwas unpräzise. Und letzteres sollte gerade bei einem mathematischen Artikel keinesfalls sein, denn in der Mathematik kann "unpräzise" oft einfach nur "falsch" bedeuten. Ein sehr merkwürdiger Teil findet sich übrigens gleich zu Beginn: "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip.". Wenn man unter dem Link nachsieht, liest sich der Satz dann so: "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, schließt sie vom Allgemeinen aufs Spezielle". Ich weiß nicht, was mir das sagen soll. Also erstmal Contra --Sentry 12:20, 12. Okt 2005 (CEST)

Pro Vielleicht könnte man noch das vielzitierte Beispiel mit den Dominosteinen einbringen: Der erste wird angeschubst, schmeißt den zweiten um, der den dritten usw. Der holprige Satz "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip." ist nicht falsch, sondern steht der Trennung zwischen logischer und mathematischer Induktion grammatisch etwas schwach entgegen: Alle Mathematik ist deduktiv, ergo auch die Vollständige Induktion. Der Name des Beweisverfahrens ist für Logiker also etwas unverständlich gewählt, beruht aber darauf, dass man von einem speziellen Fall (dem Induktionsanfang) auf die Allgemeinheit (alle natürlichen Zahlen) schließt. Innerhalb der deduktiven Mathematik liegt hier also ein (pseudo-)induktives Verfahren vor. --Thetawave 13:01, 15. Okt 2005 (CEST)

Pro --wizzar 19:59, 15. Okt 2005 (CEST)

[Bearbeiten] "Man beruft sich auf den Fall n=2 ??"

In dem Artikel steht zu dem Beweis, dass alle Zahlen gleich sind:

"Beim Induktionsschritt beruft man sich auf einen Fall, der aber nicht explizit bewiesen wurde (z.B. den Fall n = 2)" und "Wir berufen uns also auf die Richtigkeit von n = 2, ohne es vorher bewiesen zu haben"

Damit kann ich mich gar nicht einfreunden:

Der Induktionsschluss hat ÜBERHAUPT NICHTS mit der tatsächlichen Richtigkeit der einzelnen Aussagen zu tun: Es wird nur gezeigt, dass die FOLGERUNG gilt. (Die Folgerung von n auf n+1 kann sogar richtig sein, ohne das A(n) gilt!!)

Der EINZIGE Fehler in dem Beweis ist hier, dass der Induktionsschluss NUR FÜR n>=2 möglich ist, aber für ausnahmslos ALLE n>=1 gültig sein müsste!!

Explizit bewiesen wird in diesem (Schein-)Beweis nur für n=1. Würde man bei 2 anfangen wäre es ein anderer Beweis mit anderer Verankerung, das ist aber viel zu kompliziert gedacht!

Man beruft sich also höchstens im allerweitesten Sinne auf die Richtigkeit von n=2:

"Wenn A(2) gelten würde, wäre der Satz bewiesen."

Wenn ich kein gutes Gegenargument höre, ersetze ich diese seltsame Erklärung durch die meiner Meinung nach trefferende Festmachung des Fehlers:

"Der Induktionsschritt ist nicht für alle n>=n0 gültig!, d.h. es gibt mindestens ein n>=n0, für das er nicht anwendbar ist. (Hier n=1)"

Zustimmung. Es ist aber unnötig, hier über irgendein n0 zu sprechen. Der Induktionsschritt von 1 auf 2 ist falsch, mehr muss man nicht sagen.--Gunther 20:58, 6. Nov 2005 (CET)

Genau. In dem Fall muss man nicht mehr sagen. Will man eine allgemeine Einordnung des Fehlers (unter "häufige fehler und stolperfallen") angeben, so ist eben dieser Satz (s.o.) zutreffend ("schluss nicht für alle n gültig")

"Häufige Fehler" sind in einem Enzyklopädieartikel ohnehin fragwürdig (vgl. WP:WWNI Punkt 8), aber ich denke, das Beispiel hat eine gewisse eigenständige Berühmtheit erlangt und dient auch dem Verständnis der Induktion.--Gunther 15:48, 8. Nov 2005 (CET)

[Bearbeiten] Geschichtlich: frühere Verwendung der Induktion?

Im Artikel Franciscus Maurolicus findet sich ein Hinweis auf eine frühere Verwendung der Induktion. Ich kenn mich mit der Geschicht der Mathematik nicht so gut aus, dass ich sagen könnte, dass das stimmt. Vielleicht kann das jemand aufklären? Grüße --Trifi 23:46, 12. Apr 2006 (CEST)

[Bearbeiten] Ist das Induktionsprinzip deduktiv?

Schon andere Kommentatoren vor mir sind über den folgenden Satz gestolpert: "Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip." Was absurd klingt wird an anderer Stelle gerechtfertigt mit dem Hinweis, dass die gesamte Mathematik deduktiv ist, also auch ihr Induktionsprinzip. Ich möchte vorschlagen einen Unterschied zwischen internen und externen Eigeschaften zu sehen. Das Induktionsprinzip ist induktiv, denn vom Speziellen wird auf das Allgemeine geschlossen -- eine interne Eigenschaft. In der mathematischen Praxis kenne ich es als Axiom. Dieses allgemeine Axiom wird auf den speziellen Fall angewendet -- eine externe Eigenschaft. Was man, diesen Gedanken folgend, anstelle des zitierten Satzes schreiben könnte, wäre meiner Meinung nach relativ uninteressant, etwa: "Das Induktionsprinzip erlaubt einen induktiven Schluss, d.h. einen Schluss vom Speziellen aufs Allgemeine. Es wird im deduktiven Argumentieren der Mathematik als allgemeines Axiom benutzt, das im speziellen Fall seine Anwendung findet." Wie gesagt, eher uninteressant. Sollte man den Satz vielleicht komplett weglassen? Gr., Bastian

Der Satz ist wichtig und richtig; die Unterscheidung "intern" und "extern" ist unnötig und findet sich meines Wissens auch nicht in der Literatur. Zunächst solltest Du Dir klar machen, dass Axiome in der Mathematik nicht induktiv begründet werden; sie werden als "wahr" vorausgesetzt, ohne sich um die "Wirklichkeit" zu kümmern. Ausgehend von diesen Axiomen wird deduktiv weitergearbeitet, auch bei der vollständigen Induktion. Lies am besten Induktionsschluss durch, dann sollte Dir klar werden, dass vollständige Induktion mit dem Induktionsschluss der Logik nichts zu tun hat. --NeoUrfahraner 07:12, 4. Mai 2006 (CEST)

[Bearbeiten] Induktive vs. Rekursive Definition

Was ist der Unterschied? Gibt es einen?

--Christoph 17:31, 26. Sep 2006 (CEST)

Wie meinen??? *grübel* -- zOiDberg (δ·β) 17:54, 26. Sep 2006 (CEST)

Manchmal steht im Skript, dass eine Definition induktiv ist, manchmal rekursiv. Wie kann ich erkennen, wann was zutrifft. Werden rekursive Funktionen induktiv definiert? --Christoph 11:14, 27. Sep 2006 (CEST)

Hast Du Beispiele dazu? Was wird dort als induktiv, was als rekursiv bezeichnet? --NeoUrfahraner 11:33, 27. Sep 2006 (CEST)

Also ich habe den Begriff einer "induktiven Definition" bisher nocht nicht vernommen. Die Begriffe rekursiv und induktiv spielen jedoch zunächst einmal in einer ganz anderen Liga und bezeichnen unterschiedliche Dinge. Daher wären Beispiele zur Klärung Deiner Frage hilfrich. Gruß, -- zOiDberg (δ·β) 16:53, 27. Sep 2006 (CEST)

[Bearbeiten] Unterpunkt: Die Idee

Sollte der Unterpunkt "Die Idee" nicht besser dem Beispiel untergeordnet werden? Immerhin bezieht sich ja der Lösungsweg dann wieder auf das Beispiel. Hat mich beim Lesen etwas verwirrt...

[Bearbeiten] Was spricht gegen das PDF?

http://de.wikipedia.org/w/index.php?title=Induktion_%28Mathematik%29&diff=22971718&oldid=22951141

Aufgaben mit Beweisen zur Induktion (pdf)

spricht da irgendetwas gegen? Das erscheint mir doch eher hilfreich ...

[Bearbeiten] Scherzhafte vollständige Induktion

Hallo zusammen, hat jemand Quellen für scherzhafte Anwendungen der v.I., also aus völlig un-mathematischen Zusammenhängen oder witzige falsche Induktionen ? MfG Maex 15:39, 2. Jan. 2007 (CET)

Von „http://de.wikipedia.org../../../v/o/l/Diskussion%7EVollst%C3%A4ndige_Induktion_640b.html“