Frage von rotetasse, 56

Kann mir jemand den Unterschied zwischen Starker und Schwacher Induktion erklären?

In der Ausführung sind die beiden doch identisch oder? Nur die Hypothesis unterscheidet sich, oder liege ich da falsch? Ich verstehe das einfach nicht.

Antwort
von Melvissimo, 38

Bei der starken Induktion zeigt man im Induktionsschluss, dass A(n+1) gilt, wenn bereits A(1), ..., A(n) gelten. D.h. man benutzt unter Umständen alle vorherigen Aussagen und nicht nur A(n), wie es oft üblich ist.

Ein klassisches Beispiel: Jede natürliche Zahl (mindestens 2) hat eine Primfaktorzerlegung.

Beweis: Sei n eine natürliche Zahl (mindestens 2). Falls n eine Primzahl ist, sind wir fertig. Ansonsten ist n = p * q für zwei natürliche Zahlen p,q (beide mindestens 2). Insbesondere sind p und q beide kleiner als n und nach Voraussetzung haben beide eine Primfaktorzerlegung. Damit hat auch n eine Primfaktorzerlegung.

Keine passende Antwort gefunden?

Fragen Sie die Community