vollständige Induktion

Wissenschaft Mathematik
1

Hallo,

um die vollständige Induktion zu verstehen, habe ich mir aus einem Buch das folgende Beispiel angeschaut:

S=Summe

Zu beweisen: S von k=n bis 2n aus k = 3 * S von k=1 bis n aus k

  1. Induktionsanfang n=1
    zu zeigen: S von k=1 bis 2 aus k = 3* S von k=1 bis 1 aus k
    Beweis: 1+2 = 3

  2. Induktionsschritt A(n) => A(n+1)
    Voraussetzung: S von k=n bis 2n aus k = 3* S von k=1 bis n aus k

Und genau hier höre ich auf die Sache zu verstehen. Die Aussage die nach der Voraussetzung steht will ich doch gerade beweisen. Und jetzt setze ich einfach voraus, dass die stimmt? Ich habe sie doch nur für n=1 bewiesen und noch nicht für n.

Mein Problem anderst ausgedrückt:
Für mich liest sich dass so als wollte man beweisen dass a=b ist und zwar unter der Voraussetzung a=b, ich kann doch nicht was ich beweisen will als richtig annehmen um zu beweisen dass es richtig ist.
Ich komm aus diesem Denkmuster einfach nicht raus. Kann mir jemand einen Tip geben wie ich die Sache richtig sehen kann?

Vielen Dank im Voraus.

Gruß

Max

2

Hallo,

Hallo !

um die vollständige Induktion zu verstehen, habe ich mir aus
einem Buch das folgende Beispiel angeschaut:

S=Summe

Zu beweisen: S von k=n bis 2n aus k = 3 * S von k=1 bis n aus
k

also
\sum\limits_{k=n}^{2n}k=3\sum\limits_{k=1}^n k

  1. Induktionsanfang n=1
    zu zeigen: S von k=1 bis 2 aus k = 3* S von k=1 bis 1 aus k
    Beweis: 1+2 = 3

  2. Induktionsschritt A(n) => A(n+1)
    Voraussetzung: S von k=n bis 2n aus k = 3* S von k=1 bis n aus
    k

Und genau hier höre ich auf die Sache zu verstehen. Die
Aussage die nach der Voraussetzung steht will ich doch gerade
beweisen. Und jetzt setze ich einfach voraus, dass die stimmt?
Ich habe sie doch nur für n=1 bewiesen und noch nicht für n.

Du hast Recht, so formuliert ist es verwirrend. Das Entscheidende ist, dass du die Aussage der Induktionsbehauptung für alle n beweisen willst.
In der Induktionsvoraussetzung (häufig auch Induktionsannahme) nimmst du an, dass die Aussage für ein n gilt.
Du hast es für n=1 bewiesen und versuchst jetzt im Induktionsschritt (oder auch Induktionsschluss) zu zeigen, dass wenn die Aussage für ein beliebiges n gilt, sie auch für das nächste gilt.

Gruß

hendrik

3

Hey Max,

das Prinzip bei der vollständigen Induktion kann man ein wenig mit einem Dominoeffekt vergleichen.

Die Induktion besteht ja aus 3 Schritten:

Induktionsanfang:
Du überprüfst, ob die Aussage überhaupt für irgendeine Zahl stimmt.

Induktionsvoraussetzung:
Nach dem Namen ist es nur eine Voraussetzung. Manche nennen es auch Induktionsannahme. Du nimmst einfach mal an, dass es für die ersten k Zahlen stimmt. Was des k ist, weiß man ja nicht :smile:

Induktionsschritt:
Dies ist jetzt der wichtige Schritt. Wenn man annimmt, dass es für die ersten k Zahlen stimmt, musst du jetzt beweisen, dass es noch für k+1 gilt.
Hier kommt jetzt der Dominoeffekt ins Spiel: Wenn k Steine umfallen und du gezeigt hast, dass der k+1 auch noch umfällt, stimmt es automatisch für alle Zahlen.
Einfach aufgrund der Unbestimmtheit von k. Wir fangen bei k=1 an, d.h. der erste Stein fällt um. Man hat gezeigt, dass aber dann auch der zweite umfällt.
Gut, aber wenn der zweite auch umfällt, kann ich auch k=2 wählen und habe dann gezeigt, dass der dritte Stein umfällt, usw usw.

Sry, bin grad nicht so eloquent, aber ich hoffe, ich konnte bissl helfen.
Gruß René

4

Hi Hendrik, Hi TheBozz,

erstmal vielen Dank für eure Antworten. Es hat mir schon geholfen die ganze Sache besser zu verstehen. Aber ganz klar komm ich damit nicht, da die in meinem Artikel beschriebene Induktionsvoraussetzung beim nachfolgendem Beweis tatsächlich rechnerisch benutzt wird um gerade die zu beweisende Aussage allgemein für alle n zu beweisen.

Heute ist es schon zu spät darüber nachzudenken, ist nicht gut zum einschlafen geeignet. Aber ich muss mir die Sache nochmal durch den Kopf gehen lassen.

Noch eine andere Frage: Gibt es eigentlich ne simple Methode um mathematische Zeichen in Dokumenten darzustellen?

Nochmals danke für eure Antwort.

Gruß

Max

5

Hey Max,

des wird auch bei jeder vollständigen Induktion so sein :smile: Man braucht, um den Induktionsschritt zu führen auf jeden Fall die Induktionsannahme/-voraussetzung.

Wenn wir des grad nochmal an dem Dominoeffekt veranschaulichen wollen:
Du musst annehmen, dass die ersten k Steine umfallen, um zu beweisen, dass auch der k+1 Stein umfällt.
Sollten die ersten k Steine nicht umfallen, warum dann der k+1?

Und dadurch, dass des k beliebig war, muss es für alle Zahlen gelten.

Einfach mal drüber schlafen :wink:
Gute Nacht
Gruß René

PS: Die simple Methode mathematische Formeln hier im Forum darzustellen, ist Latex. Hier kannst du nachlesen, wie es funktioniert:
http://www.wer-weiss-was.de/app/faqs/classic?entries…

6

Hallo Max,

Aber ganz klar
komm ich damit nicht, da die in meinem Artikel beschriebene
Induktionsvoraussetzung beim nachfolgendem Beweis tatsächlich
rechnerisch benutzt wird um gerade die zu beweisende Aussage
allgemein für alle n zu beweisen.

Das wird immer so gemacht und gehört zur Methode.
In diesem Schritt zeigst du auch nur allgemein, dass wenn die Aussage für n richtig ist, sie auch für n+1 stimmt. An diesem Punkt interessiert dich gar nicht, ob die Aussage für alle n stimmt oder nicht.

Du sagst an dieser Stelle einfach: Ich gehe davon aus, dass die Aussage für eine beliebige Zahl n stimmt. Dann versuchst du zu zeigen, dass sie dann auch für (n+1) stimmt.

Jetzt kommt der Einwand, dass man doch gar nicht weiß, ob die Aussage für n gilt.
Du weißt aber schon, dass die Aussage für dein erstes n (z.B. n=1) gilt (war dein Induktionsanfang).

Also: n=1 => Aussage stimmt => Dann stimmt die Aussage auch für n=2 => dann stimmt die Aussage auch für n=3 => … => Dann stimmt die Aussage für alle n

Viele Grüße
Kati

2 „Gefällt mir“
7

Hallo,

um die vollständige Induktion zu verstehen, habe ich mir aus
einem Buch das folgende Beispiel angeschaut:

Ich komm aus diesem Denkmuster einfach nicht raus. Kann mir
jemand einen Tip geben wie ich die Sache richtig sehen kann?

Vielleicht hilft es Dir, statt des allgemeinen „n“ in der Induktionsvoraussetzung mal eine konkrete Zahl einzusetzen, aber dann nicht ausrechnen, sondern umformen.

Zuerst kannst Du ja durch probieren herausbekommen, dass die Formel nicht nur für 1, sondern auch für 2 und 3 stimmt. Du WEISST also, dass sie für 3 gilt (das ist dann ja keine Annahme mehr).

Nun nehme Dir die 4 vor. Schreibe dazu die Summe bis 4, rechne sie aber nicht einfach aus, sondern teile die Summe so auf, dass sie geschrieben werden kann als eine Summe bis 3 und dann noch ein paar Terme dazu.

Für die Summe bis 3 setze das bekannte Ergebnis ein und stelle dadurch fest, dass die Formel auch für 4 gilt.

Das könntest Du jetzt bis unendlich fortsetzen, aber so viel Zeit hast Du nicht.

Daher nimm einfach an, Du hast dieses Verfahren bis zu einer beliebigen Zahl k durchgeführt und machst den Schritt nach k+1 nun, ohne genau zu sagen, was k ist. Methodisch geht das aber genauso als würdest Du von 3->4 oder 4->5 oder … gehen.

Konkretes Rechnen hilft oft um zu verstehen, wie Mathematiker denken. Die rechnen „eigentlich“ auch konkret, aber versuchen, statt der konkreten Zahlen eben Buchstaben zu setzen, für die beliebiege Zahlen eingesetzt werden können.

Gruß
Thomas

8

Hallo heureka,

vielen Dank für deine Antwort. Deine Art die Methode zu beschreiben hat genau mein Problem getroffen. Jetzt hab ich es glaube ich kapiert.

Auch nochmal danke an alle anderen für eure Antworten.

Beste Grüße

Max

9

Moin!

Noch eine andere Frage: Gibt es eigentlich ne simple Methode
um mathematische Zeichen in Dokumenten darzustellen?

Joa, die gibt es: LaTeX .
Die Grundzüge von LaTeX, die du z.B hier im Forum dann verwenden kannst, findest du in den FAQ beschrieben. Ansonsten einfach mal googeln, gibt ganz viele Tutorials und Anleitungen zu LaTeX.

Liebe Grüße
Daniel