Frage von vin030, 34

Kann mir jemand ausführlich die Vollständige Induktion erklären?

Antwort
von Kreuzzzfeuer, 18

Eine Vollständige Induktion ist eine Beweismethode. Mit dieser möchte man zeigen, dass etwas für alle natürlichen Zahlen n gilt (z.B. eine Formel), indem du zeigst, dass, wenn es für ein n gilt, es auch für den Nachfolger n+1 gilt (also daher für alle n). Das läuft in der Regel so ab:

Man hat eine Vermutung, z.B. eine rekursive Zahlenfolge und vermutet eine explizite Zahlenfolge, dann kann man diese mit der vollständigen Induktion beweisen.

  1. Induktionsanfang: Hier probierst du deine Vermutung für n = 0, n = 1 und n = 2 aus. Denn es muss natürlich überhaupt erstmal für etwas gelten, sonst könntest du ohne Induktionsanfang beweisen, dass alle ungeraden Zahlen = 2k sind. 
  2. Induktionsvoraussetzung: Du sagst also, dass es für n funktioniert. Also schreibst du die Vermutung hin und setzt sie voraus. Also a_n = .... (deine Vermutung, wie du explizit das n-te Glied der Folge bestimmst). 
  3. Induktionsbehauptung: Jetzt kommt der Teil, den du beweisen willst. Also, dass es auch für n+1 dann gilt. Also a_n+1 = .... (hierbei nimmst du die gleiche Formel wie bei der Voraussetzung, ersetzt aber jedes "n" mit einem "n+1")
  4. Induktionsschritt: Alles vorher war eigentlich nur Aufschreibearbeit. Jetzt musst du versuchen von der Voraussetzung auf die Behauptung zu schließen. Wenn also die rekursive Vorschrift a_n+1 = a_n * 3 - 2 ist, dann musst du nun zeigen, dass a_n * 3 - 2 das gleiche ist, wie die explizite Vorschrift für n+1 (also die Behauptung). Man setzt eigentlich immer die Voraussetzung dafür ein (du könntest hier jetzt also statt a_n die explizite Form einsetzen). Dann musst du halt meist ein bisschen umformen und wenn dann die Behauptung rauskommt, ist der Beweis fertig! :)

qed :D

Kommentar von vin030 ,

Dankeschön ^^

Keine passende Antwort gefunden?

Fragen Sie die Community