Direkt zum Inhalt

Pfadnavigation

  1. Startseite
  2. Mathematik
  3. 2 Grundbegriffe der Mathematik
  4. 2.1 Aussagen
  5. 2.1.6 Sätze und Beweise
  6. Beweise, vollständige Induktion

Beweise, vollständige Induktion

Das Verfahren der vollständigen Induktion hängt eng zusammen mit der Menge der natürlichen Zahlen bzw. mit Teilmengen natürlicher Zahlen. Es ist immer dann anwendbar, wenn man auf Aussagen trifft, die für alle natürlichen Zahlen gelten, also die die folgende Struktur aufweisen:
Für alle natürlichen Zahlen n       ( m i t       n ≥ n 0 ) gilt H ( n ) .

Schule wird easy mit KI-Tutor Kim und Duden Learnattack

  • Kim hat in Deutsch, Mathe, Englisch und 6 weiteren Schulfächern immer eine von Lehrkräften geprüfte Erklärung, Video oder Übung parat.
  • 24/7 auf Learnattack.de und WhatsApp mit Bildupload und Sprachnachrichten verfügbar. Ideal, um bei den Hausaufgaben und beim Lernen von Fremdsprachen zu unterstützen.
  • Viel günstiger als andere Nachhilfe und schützt deine Daten.
Jetzt 30 Tage risikofrei testen
Your browser does not support the video tag.

Das Verfahren der vollständigen Induktion hängt eng zusammen mit der Menge der natürlichen Zahlen bzw. mit Teilmengen natürlicher Zahlen. Es ist immer dann anwendbar, wenn man auf Aussagen trifft, die für alle natürlichen Zahlen gelten, also die die folgende Struktur aufweisen:

Für alle natürlichen Zahlen n       ( m i t       n ≥ n 0 ) gilt H ( n ) .

Das Verfahren beruht auf der sogenannten Induktionseigenschaft der natürlichen Zahlen. Diese ist Bestandteil des peanoschen Axiomensystems und lautet:

Ist T eine Teilmenge von ℕ und gilt
  (   I   )     1 ∈ T   (   I I   )   F ü r       a l l e       n ∈ ℕ       g i l t :       n ∈ T ⇔ n + 1 ∈ T ,
dann ist T = ℕ .

Es sei T = { n :       H ( n ) } die Menge aller natürlichen Zahlen, für die eine Aussage H ( n ) wahr ist.
Anwenden der Induktionseigenschaft besagt dann das Folgende.
Wenn man zeigen kann
  a )         H (   1   )       i s t       w a h r ,       d .   h .       1 ∈ T .   b )         F ü r       a l l e       n       g i l t :       W e n n       H ( n )       w a h r       i s t ,       s o       i s t       H ( n + 1 )       w a h r .           n ∈ T ⇒ n + 1 ∈ T       f ü r       a l l e       n ∈ ℕ
dann gilt (aufgrund der als Axiom angenommenen Induktionseigenschaft) T = ℕ , was wiederum bedeutet H ( n ) ist für alle n ∈ ℕ gültig.

Um die Allgemeingültigkeit einer Aussage H ( n ) über ℕ nachzuweisen, hat man also beim Beweis durch vollständige Induktion zwei Schritte zu vollziehen:

  • Induktionsanfang
    Man zeigt, dass H (   1   ) wahr ist.
  • Induktionsschritt
    Man zeigt, dass für alle n ∈ ℕ gilt: Aus der Annahme, H ( n ) sei richtig, kann auf die Gültigkeit von H ( n + 1 ) geschlossen werden, d. h.:
      H ( n ) ⇒ H ( n + 1 )       f ü r       a l l e       n ∈ ℕ
    (Inhalt des Induktionsschrittes ist also eine Implikation A ⇒ B . Das Vorderglied heißt Induktionsvoraussetzung und das Hinterglied dieser Implikation ist die Induktionsbehauptung.)

Wichtig ist, dass beide Schritte verifiziert werden müssen, d. h. als wahr nachzuweisen sind: sowohl der Induktionsanfang (es muss erst einmal eine natürliche Zahl geben, für die H ( n ) gilt) als auch der Induktionsschritt oder Induktionsschluss (Nachweis der obigen Implikation). Erst dann gilt, dass H ( n ) für alle wahr n ∈ ℕ ist.

Die Struktur des Beweises durch vollständige Induktion sieht formal also folgendermaßen aus:
  H (   1   ) ∧ [ F ü r       a l l e       n ∈ ℕ :       H ( n ) ⇒ H ( n + 1 ) ] ⇒ [ F ü r       a l l e       n ∈ ℕ :       H ( n ) ]   o d e r   H ( n 0 ) ∧ [ F ü r       a l l e       k ∈ ℕ :       H ( k ) ⇒ H ( k + 1 ) ] ⇒ [ F ü r       a l l e       n ≥ n 0 :       H ( n ) ]

Beispiel 1:

Man beweise durch vollständige Induktion:
∑ i     =     1 n i   3 = 1 3 + 2 3 + 3 3 + ... + n 3 = [ n ( n + 1 ) 2 ] 2

  • Induktionsanfang
    n = 1   :         ∑ i     =     1 1 i   3 = 1   3 = ( 1 ( 1 + 1 ) 2 ) 2                               1 = 1
  • Induktionsschritt
    Induktionsvoraussetzung (n = k):
    Es gelte ∑ i     =     1 k i   3 = 1 3 + 2 3 + 3 3 + ... + k 3 = [ k ( k + 1 ) 2 ] 2 .
    Induktionsbehauptung (n = k + 1):
    Es sei ∑ i     =     1 k   +   1 i ‌ 3 = 1   3 + 2 3 + 3 3 + ... + k 3 + ( k + 1 ) 3 = [ ( k + 1 ) ( k + 2 ) 2 ] 2 .
    Induktionsbeweis:
    ∑ i     =     1 k   +   1 i   3 = ∑ i     =     1 k i   3 + ( k + 1 ) 3         = [ k ( k + 1 ) 2 ] 2 + ( k + 1 ) 3         = k 2 ( k + 1 ) 2 + 4 ( k + 1 ) 3 4 = k 2 ( k + 1 ) 2 + 4 ( k + 1 ) 2 ⋅ ( k + 1 ) 4         = ( k + 1 ) 2 ⋅ ( k 2 + 4 k + 4 ) 4 = ( k + 1 ) 2 ⋅ ( k + 2 ) 2 4         = [ ( k + 1 ) ⋅ ( k + 2 ) 2 ] 2

Beispiel 2:

Man beweise: Für alle n ∈ ℕ gilt 133   |   ( 11   n + 2 + 12   2 n + 1 ) .

  • Induktionsanfang
    n = 0     :       11 2 + 12 = 133     ⇒     133   |   133
  • Induktionsschritt
    Induktionsvoraussetzung (n = k − 1):
    Es gelte 133   |   ( 11   k + 1 + 12 2 k − 1 ) .
    Induktionsbehauptung (n + 1 = k):
    Dann sei auch 133   |   ( 11   k + 2 + 12   2 k + 1 ) .
    Induktionsbeweis:
    11   k + 2 + 12   2 k + 1 = 11   k + 1 ⋅ 11 + 12 2 k − 1 ⋅ 12 2 = 11   k + 1 + 10 ⋅ 11   k + 1 + 12 2 k − 1 + 143 ⋅ 12 2 k − 1 = 11   k + 1 + 12 2 k − 1 + 10 ⋅ 11   k + 1 + 143 ⋅ 12 2 k − 1 = 11   k + 1 + 12 2 k − 1 + 10 ( 11   k + 1 + 12 2 k − 1 ) ⏟ n a c h       V o r a u s s e t z u n g ‌ ‌ ‌       d u r c h       133       t e i l b a r + 133 ⋅ 12 2 k − 1
    Folglich gilt 133   |   ( 11   n + 2 + 12   2 n + 1 ) .
Lernhelfer (Duden Learnattack GmbH): "Beweise, vollständige Induktion." In: Lernhelfer (Duden Learnattack GmbH). URL: http://www.lernhelfer.de/schuelerlexikon/mathematik/artikel/beweise-vollstaendige-induktion (Abgerufen: 20. May 2025, 18:12 UTC)

Suche nach passenden Schlagwörtern

  • Ausssagen
  • peanosches Axiomensystem
  • natürliche Zahlen
  • Peano
  • Beweisen
  • Teilbarkeit
Jetzt durchstarten

Lernblockade und Hausaufgabenstress?

Entspannt durch die Schule mit KI-Tutor Kim und Duden Learnattack.

  • Kim hat in Deutsch, Mathe, Englisch und 6 weiteren Schulfächern immer eine von Lehrkräften geprüfte Erklärung, Video oder Übung parat.
  • 24/7 auf Learnattack.de und WhatsApp mit Bildupload und Sprachnachrichten verfügbar. Ideal, um bei den Hausaufgaben und beim Lernen von Fremdsprachen zu unterstützen.
  • Viel günstiger als andere Nachhilfe und schützt deine Daten.

Verwandte Artikel

Logische Operationen mit Aussagen

Aussagen können negiert oder durch aussagenlogische Operationen (Konjunktion, Disjunktion, Alternative, Implikation, Äquivalenz) miteinander verknüpft werden.
Der Wahrheitswert einer negierten oder zusammengesetzten Aussage hängt dabei ausschließlich vom Wahrheitswert der Ausgangsaussage bzw. der verknüpften Teilaussagen ab.

Axiomensysteme

Durch Axiomensysteme werden mathematische Begriffe mithilfe einer Reihe von einfachen Festlegungen, die man Axiome nennt, charakterisiert.
An ein mathematisches Axiomensystem werden eine Reihe von Bedingungen gestellt. So sollte es z.B. widerspruchsfrei sein.

Beweisverfahren der vollständigen Induktion

Das Verfahren der vollständigen Induktion hängt eng zusammen mit der Menge der natürlichen Zahlen bzw. mit Teilmengen natürlicher Zahlen. Es ist immer dann anwendbar, wenn man auf Aussagen trifft, die für alle natürlichen Zahlen gelten, also die die folgende Struktur aufweisen:

  • Für alle natürlichen Zahlen n       ( m i t       n ≥ n 0 ) gilt H ( n ) .

Friedrich Ludwig Gottlob Frege

* 08.11.1848 Wismar
† 26.07.1925 Bad Kleinen

GOTTLOB FREGE arbeitete an der Universität Jena. Er war maßgeblich an der Schaffung von Grundlagen der Logik beteiligt, wobei er an Ideen des englischen Mathematikers GEORGE BOOLE anknüpfte. FREGES Ideen wiederum waren Grundlage für GIUSEPPE PEANO und BERTRAND RUSSELL.

Earl of Bertrand Arthur William Russell

* 18. Mai 1872 Ravenscroft Trellek, Monmouthshire, Wales
† 2. Februar 1970 Penrhyndeudraeth Merioneth, Wales

BERTRAND RUSSELL ist Mitbegründer der modernen mathematischen Logik. Im Jahre 1901 fand er die nach ihm benannte Antinomie der Menge aller Mengen, die sich nicht selbst enthalten.
RUSSELL veröffentlichte zudem zahlreiche philosophische Schriften und Essays.

Ein Angebot von

Footer

  • Impressum
  • Sicherheit & Datenschutz
  • AGB
© Duden Learnattack GmbH, 2025