Unterschied zwischen allgemeiner und vollständiger Induktion

Neue Frage »

brainless Auf diesen Beitrag antworten »
Unterschied zwischen allgemeiner und vollständiger Induktion
hallo,

was ist der Unterschied zwischen allgemeiner und vollständiger Induktion ? Erstaunt2

ich soll eine Aufgabe nach allgemeiner Induktion beweisen...
bei vollständiger hätte ich für z.B. bewiesen und danach für
aber wie geht man bei der allgemeinen Induktion vor?

aufgeschrieben hatte ich mir: Verwendet im Induktionsschritt Gültigkeit von mit

aber was fängt man jetzt damit an?
Abakus Auf diesen Beitrag antworten »
RE: Unterschied zwischen allgemeiner und vollständiger Induktion
Hallo!

Zitat:
Original von brainless
aufgeschrieben hatte ich mir: Verwendet im Induktionsschritt Gültigkeit von mit


Da stehts. Gemeint ist eine etwas allgemeinere IV: die Behauptung wird nicht nur für n angenommen, sondern sogar für alle Zahlen von 1 bis n. Manchmal kann das nützlich sein.

Grüße Abakus smile
Jacques Auf diesen Beitrag antworten »

Hallo,

Bei der allgemeinen („starken“) Induktion braucht man keinen Induktionsanfang, so lange die Aussage für alle natürlichen Zahlen gilt.


Die normale Induktion funkioniert ja so:

(1) Die Aussage gilt für 1 (Induktionsanfang)

(2) Für alle natürlichen Zahlen gilt: Ist die Aussage für n wahr, dann auch für n +1 (Induktionsschritt)


Bei der starken Induktion muss man nur zeigen:

Für alle natürlichen Zahlen n gilt: Wenn die Aussage für alle natürlichen Zahlen k < n gilt, dann auch für n.
brainless Auf diesen Beitrag antworten »

danke..
Zitat:
Original von Jacques
Bei der starken Induktion muss man nur zeigen:

Für alle natürlichen Zahlen n gilt: Wenn die Aussage für alle natürlichen Zahlen k < n gilt, dann auch für n.
wie zeigt man sowas? habe bisher noch nie allgm induk. gemacht und deswegen kein plan verwirrt

vllt. kann mir da jmd an einem beispiel erklären:
(Wie oft muss man etwas brechen, um entsprechend viele Teile zuhaben)

ich hätte jetzt so angefangen:
Induktionsanfang:
für
für 1 Teil muss man 0mal breche. erfüllt.
Induktionsschritt:
und wie zeige ich jetzt, dass die Aussage oben auch für für alle mit gilt? Erstaunt2
AD Auf diesen Beitrag antworten »
Einspruch
Alles was ihr hier als Eigenschaften von "allgemeiner Induktion" und "vollständiger Induktion" auflistet, gehört m.E. alles unter den Oberbegriff "vollständige Induktion". Augenzwinkern


Zitat:
Zitat aus http://de.wikipedia.org/wiki/Induktion_%28Denken%29 :

"Allgemeine Induktion" bezeichnet den Schluss von mehreren Beobachtungen auf eine Regel (wenn man z. B. glaubt, ein Muster zu erkennen)


Aber offenbar gibt es da unterschiedliche Ansichten, na von mir aus. Augenzwinkern
Jacques Auf diesen Beitrag antworten »

An brainless:

Bei der „starken Induktion“ brauchst Du, wie gesagt, keinen Induktionsanfang zu machen, wenn die Aussage für alle natürlichen Zahlen bewiesen werden muss.

Denn wenn die Aussage



gezeigt ist, dann ist durch den Fall n = 1 automatisch der Induktionsanfang gegeben: Es existieren gar keine natürlichen Zahlen k < 1, also ist der Teil „A(k) für alle k < 1“ wahr, und dann gilt nach der obigen Aussage auch A(1).


Sonst funktioniert die Induktion praktisch so wie bei der „klassischen“ Variante:

Sei n eine natürliche Zahl. Du setzt voraus, dass die Aussage für alle natürlichen Zahlen k < n gilt und musst sie damit für n selber zeigen.

Also man setzt die Richtigkeit nicht nur für den direkten Vorgänger n-1 voraus wie bei der „klassischen Induktion“, sondern für alle natürlichen Zahlen, die kleiner als n sind; für n-1, n-2, n-3 u. s. w. Das ist dann wichtig, wenn z. B. eine Folge induktiv definiert ist und dabei nicht nur das direkte Vorgänger-Glied in der Definition auftritt, sondern auch der Vorvorgänger.
 
 
brainless Auf diesen Beitrag antworten »

Zitat:
Original von Jacques
Sonst funktioniert die Induktion praktisch so wie bei der „klassischen“ Variante:

Sei n eine natürliche Zahl. Du setzt voraus, dass die Aussage für alle natürlichen Zahlen k < n gilt und musst sie damit für n selber zeigen.
so _langsam_ verstehe ich..

ich muss sie "nur für n selber zeigen" heißt: ich solls allgmein für "n" zeigen oder mit nem konkreten Wert für n? und dann gilt dass automatisch für alle k < n oder muss ich dass nochmal beweisen??? verwirrt
Jacques Auf diesen Beitrag antworten »

Du betrachtest eine unbestimmte natürliche Zahl „n“. Dann setzt Du voraus, dass die Aussage für alle natürlichen Zahlen k < n gilt, also für n-1, n-2, ..., 1. Mit dieser Voraussetzung musst Du die Aussage für n zeigen. Also gegeben ist A(k) für alle k < n. Zeigen musst Du A(n).

Vergleiche doch mit der „klassischen“ Variante der Induktion:

Da zeigst Du zuerst, dass die Aussage für 1 gilt. Dann betrachtest Du eine unbestimmte natürliche Zahl „n“ und setzt voraus, dass die Aussage für n-1 gilt. Mit dieser Voraussetzung musst Du die Aussage für n zeigen.


Also die starke Induktion ist wirklich nur eine etwas andere Variante der „klassischen“ vollständigen Induktion. Der Induktionsanfang fällt weg, und man setzt im Induktionsschritt die Richtigkeit der Aussage für alle Zahlen n-1, n-2, ..., 1 voraus, nicht nur für n-1.
brainless Auf diesen Beitrag antworten »

Zitat:
Original von Jacques
Du betrachtest eine unbestimmte natürliche Zahl „n“. Dann setzt Du voraus, dass die Aussage für alle natürlichen Zahlen k < n gilt, also für n-1, n-2, ..., 1. Mit dieser Voraussetzung musst Du die Aussage für n zeigen. Also gegeben ist A(k) für alle k < n. Zeigen musst Du A(n).


kann mir das jemand bitte an diesem Beispiel mal erklären? Hilfe
(Wie oft muss man etwas zerbrechen, um entsprechend viele Teile zuhaben - z.B. Schokolade)


wie zeigt man, dass S(n) = n - 1 für k < n gilt ?
Jacques Auf diesen Beitrag antworten »

Tut mir leid, aber Du scheinst die Antworten gar nicht richtig zu lesen. Und warum Du jetzt wieder den eigentlich schon geklärten Fehler machst, die gegebene Voraussetzung mit der zu beweisenden Behauptung zu verwechseln, ist mir auch nicht klar. unglücklich


Nochmal allgemein:

Du setzt die Richtigkeit der Aussage für alle Zahlen k mit k < n voraus. Also diesen Teil beweist Du nicht, sondern Du setzt ihn als wahr voraus! So wie Du bei der klassischen Induktion voraussetzen würdest, dass die Aussage für n-1 gilt.

Von der Voraussetzung, dass die Aussage für alle k < n gilt, musst Du jetzt auf die Richtigkeit für n schließen.


Also dass

S(k) = k - 1

für alle k < n gilt, ist gegeben. So wie bei der normalen Induktion gegeben wäre, dass S(n-1) = n - 2 gilt.

Mit der obigen Voraussetzung musst Du jetzt folgern, dass auch

S(n) = n - 1

wahr ist.

Du kannst, wie gesagt, dabei die Richtigkeit von S(n-1) = n - 2, S(n-2) = n - 3 u. s. w. benutzen – wobei Du sicher mit S(n-1) auskommen wirst, genau wie bei der klassischen Induktion.



// Noch als Beispiel:

Zu beweisen ist, dass



für alle natürlichen Zahlen n gilt.



Klassische Induktion

Induktionsanfang

Behauptung:



Nachweis:




Induktionsschritt

Sei n eine beliebige natürliche Zahl > 1

Voraussetzung:

Die Aussage gilt für n-1, d. h., es gilt



Behauptung:

Die Aussage gilt auch für n; also



Nachweis der Behauptung:





Starke Induktion

Man braucht keinen Induktionsanfang, weil die Aussage für alle natürlichen Zahlen nachgewiesen werden soll und kann. Man fängt also direkt mit dem Schluss von k (k < n) auf n an.


Sei n eine natürliche Zahl

Voraussetzung:

Für alle k < n gilt die Aussage, also



Behauptung:

Die Aussage ist auch für n wahr, also



Nachweis der Behauptung:

... und jetzt kann man genau wie oben verfahren, d. h. etwa die Summe



wieder in



aufspalten und bei



die Voraussetzung benutzen.

Also bei diesem speziellen Beweis bringt die starke Induktion keinen echten Vorteil, weil man nur die Richtigkeit der Aussage beim direkten Vorgänger von n benutzt, wie man es auch bei der klassischen Induktion tut. Die vorausgesetzte Richtigkeit von S(n-2), S(n-3) u. s. w. kommt gar nicht zum Zug.

Der einzige Unterschied in dem Fall ist, dass man bei der starken Induktion eben keinen Induktionsanfang braucht.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »