Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Tipps zur vollständigen Induktion

Tipps zur vollständigen Induktion

Schüler Gesamtschule, 13. Klassenstufe

Tags: Diskrete Mathematik, Tipps, Vollständig Induktion

alumno aktiv_icon

22:42 Uhr, 10.11.2011

Könnt ihr mir in einfachen Worten die vollständige Induktion erklären?
Ein Schema zum Grunaufbau wäre hilfreich..

Außerdem wäre es nett, wenn man mir sagen könnte, wie man genau vorgehen muss, welche Schritte

z . B

nur ''Aufschreib-Schritte''sind und welche Umformungen benötigen(woran erkenne ich, wie ich umformen muss? Und woran ich erkenne, wann ich mit den Beweisverfahren zu Ende bin?..)

Ich bedanke mich schonmal im Vorraus

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

Sams83 aktiv_icon

09:11 Uhr, 11.11.2011

Hallo,

das Prinzip der vollständigen Induktion funktioniert so, dass Du zuerst einmal zeigst, dass die Formel, die Du beweisen willst, für einen Anfangswert (üblichereise

n = 1)

gilt. (Manche Formeln gelten auch erst für

z . B

n \geq 4,

dann ist das Dein Anfangswert.)
Dieser erste Schritt ist üblicherweise ein Einzeiler, also sehr einfach.

Wenn Du gezeigt hast, dass die Formel mit diesem konkret eingesetzten Anfangswert gilt, folgt die eigentliche Arbeit: Du musst zeigen, dass wenn die Formel für

n

gilt, sie auch für

n + 1

gilt.

Wenn Du dies beweisen kannst, folgt, dass sie für alle

n

gilt. Denn Du hast ja am Anfang gezeigt, dass sie für

n = 1

gilt. Da du bewiesen hast, dass sie nun auch für

n + 1

gilt, gilt sie also auch für

n = 2

. Wenn sie aber für

n = 2

gilt, gilt sie wiederum für

n + 1,

also

n = 3

. Usw, usw.

Der Beweis funktioniert also so, dass Du die Formel als gegeben für

n

annimmst. Zu beweisen ist dann die Formel für

(n + 1)

.
Üblicherweise geht man so vor, dass man die Formel mi

n + 1

aufschreibt, und dann zeigt, dass beide Seiten der Gleichung gleich sind,

z . B .,

indem man beide Seiten umformt. Es gibt auch die Möglichkeit, nur die erste Hälfte der Gleichung aufzuschreiben, und diese umzuformen, so dass die zweite herauskommt.
Ersteres Vorgehen vom parallelen Umformen beider Seiten ist aber meist gedanklich leichter.
Irgendwo in diesen Umformungen (meist ziemlich zu Anfang) sollte die Vorraussetzung (nämlich die Formel für

n)

eingesetzt werden, sonst macht das ganze Prinzip ja keinen Sinn.

Ich hoffe, das hilft weiter...ansonsten hier auch noch ein Beispiel:
http://de.wikibooks.org/wiki/Mathe_f%C3%BCr_Nicht-Freaks:_Vollst%C3%A4ndige_Induktion

Bei weiteren Fragen bitte fragen.

Bummerang

11:15 Uhr, 11.11.2011

Hallo,

"...

z . B .,

indem man beide Seiten umformt", "Ersteres Vorgehen vom parallelen Umformen beider Seiten ist aber meist gedanklich leichter."

. .

. aber auch kein korrektes Vorgehen, wenn man innerhalb der Umformungen nichtäquivalente Umformungen durchführt! Geht man von der Induktionsbehauptung für

n + 1

aus und formt die Gleichung auf beiden Seiten um, so kann man aus der falschen Behauptung am Ende auf etwas wahres schließen ohne einen Fehler gemacht zu haben. Es war dann halt nur mindestens eine Umformung nichtäquivalent. Wer mit äquivalenten und nichtäquivalenten Umformungen ein Problem hat, sollte entweder den zweiten Weg gehen oder die Schritte des ersten Weges nur auf einen Schmierblatt notieren und in der Reinschrift den Beweis von unten nach oben notieren und bei jedem Schritt die Prüfung übernehmen, ob der Schritt auch korrekt ist,

d . h

. der Schritt von oben nach unten auch umkehrbar ist.

Sams83 aktiv_icon

18:04 Uhr, 11.11.2011

Stimmt, wichtiger Hinweis! Danke, meinte natürlich Äquivalenzumformungen :-)

alumno aktiv_icon

15:20 Uhr, 15.11.2011

Danke für eure Antworten.

Jedoch sind mir die Umformungen nicht klar in dem Link vom Sams83..

Wie kommt man denn von

k \cdot (k + 1) + 2 (k + 1)

auf

(k + 1) + (k + 2)

?

Wie zeige ich die vollständige Induktion zum Beispiel an

13 n < 2^{n},

dass für alle

n

größer/gleich 7 diese Ungleichung gilt?

Sams83 aktiv_icon

15:25 Uhr, 15.11.2011

Hallo,

da wird

(k + 1)

ausgeklammert:

k (k + 1) + 2 (k + 1) = (k + 1) \cdot (k + 2)

Zwischen den beiden Termen steht ein

\cdot,

kein

+

Versuche Dich doch mal selber an Deinem Beispiel. Fange mit dem Induktionsanfang an, also zeige, dass die Formel für

n

größer/gleich 7 gilt.

Anschließend stelle die zu beweisende Formel für

n + 1

auf. Schaffst Du es bis dahin schon einmal allein?

alumno aktiv_icon

15:36 Uhr, 15.11.2011

Induktionsanfang:

n = 713 \cdot 7 = 91 < 2^{7} = 128

also ist das richtig

Induktionsschritt: (Annahme) festes, aber beliebiges

n

größer/gleich 7

13 (n + 1) = 13 n + 13 < 2^{n} + 13

?? oder muss ich jetzt auch für hoch

n

das

+ 1

einsetzen?

Sams83 aktiv_icon

15:41 Uhr, 15.11.2011

Induktionsanfang ist richtig.
Zu zeigen wäre nun, dass

13 (n + 1) < 2^{n + 1}

.

Die Voraussetzung, dass

13 n < 2^{n}

ist, darfst Du benutzen (hast Du ja auch schon richtig gemacht.

Deine Umformschritte sind soweit also schon richtig und auch zielführend, Du musst jetzt nur noch weitere Schritte rechts anschließen (entweder mit = oder

< -

zeichen), so dass sich letztendlich die Behauptung

13 (n + 1) < 2^{n + 1}

beweist.

D . h

. Du musst zeigen, dass

2^{n} + 13 < 2^{n + 1}

Ok?

alumno aktiv_icon

15:51 Uhr, 15.11.2011

Warum muss ich

2^{n} + 13 < 2^{n} + 1

zeigen? Muss hinter der

2^{n} + 1

nicht noch die

13

stehen?

Sams83 aktiv_icon

16:08 Uhr, 15.11.2011

Nein,

Deine Formel, die Du beweisen willst ist:

13 n < 2^{n}

Der Induktionsschritt ist also, zu zeigen, dass es auch für das nächstgrößere

n

gilt, also dass folgende Formel gilt:

13 (n + 1) < 2^{n + 1}

alumno aktiv_icon

21:37 Uhr, 16.11.2011

Stimmt.. Habe mich vertan.

Aber trotzdem ich das jetzt irgendwie nicht umgeformt

: (

Sams83 aktiv_icon

21:55 Uhr, 16.11.2011

Tipp:

2^{n + 1} = 2 \cdot 2^{n} = 2^{n} + 2^{n}

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

940405

937765

	Status: nicht eingeloggt	Noch nicht registriert?