# Vollständige Induktion

Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird. Da es sich um unendlich viele Zahlen handelt, kann solch ein Beweis nicht für jede Zahl einzeln erbracht werden. Er wird daher in zwei Etappen durchgeführt: als Induktionsanfang für eine kleinste Zahl (meist 1 oder 0) und als Induktionsschritt, der aus der Aussage für eine variable Zahl die entsprechende Aussage für die nächste Zahl logisch ableitet. Damit ist schon die Gültigkeit der Aussage für alle natürlichen Zahlen gezeigt.
Die Beweismethode beruht auf dem Prinzip der vollständigen Induktion (kurz: Induktionsprinzip), das entweder als Axiom gesetzt oder aus anderen Axiomen hergeleitet werden kann. Die vollständige Induktion ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik. Trotz ihres Namens handelt es sich bei der vollständigen Induktion um ein deduktives Verfahren.


## Beschreibung
Um zu beweisen, dass eine Aussage 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 für alle natürlichen Zahlen 
  
    
      
        n
      
    
    {\displaystyle n}
  
 gilt, genügt es, Folgendes zu zeigen:

Es gilt 
  
    
      
        A
        (
        0
        )
      
    
    {\displaystyle A(0)}
  
 bzw. 
  
    
      
        A
        (
        1
        )
      
    
    {\displaystyle A(1)}
  
. (Induktionsanfang, Induktionsverankerung)
Für beliebiges 
  
    
      
        n
      
    
    {\displaystyle n}
  
 folgt aus der Gültigkeit von 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 die Gültigkeit von 
  
    
      
        A
        (
        n
        +
        1
        )
      
    
    {\displaystyle A(n+1)}
  
. (Induktionsschritt, Induktionsschluss, Schluss von n auf n+1)
Im Induktionsschritt geht man so vor, dass man zunächst für ein beliebiges 
  
    
      
        n
      
    
    {\displaystyle n}
  
 die Gültigkeit von 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 voraussetzt (Induktionsvoraussetzung oder Induktionsannahme) und darauf basierend zeigt, dass 
  
    
      
        A
        (
        n
        +
        1
        )
      
    
    {\displaystyle A(n+1)}
  
 gilt (Induktionsbehauptung).


## Veranschaulichung
Die Methode der vollständigen Induktion ist mit dem Dominoeffekt vergleichbar: Wenn der erste Dominostein fällt und durch jeden fallenden Dominostein der nächste umgestoßen wird, wird schließlich jeder Dominostein der unendlich lang gedachten Kette irgendwann umfallen.
Die Allgemeingültigkeit einer Aussageform 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 ist für 
  
    
      
        n
        =
        1
        ,
        2
        ,
        3
        ,
        …
      
    
    {\displaystyle n=1,2,3,\ldots }
  
 bewiesen, wenn 
  
    
      
        A
        (
        1
        )
      
    
    {\displaystyle A(1)}
  
 gültig ist (der erste Stein fällt um) und wenn zusätzlich gilt 
  
    
      
        A
        (
        n
        )
        ⇒
        A
        (
        n
        +
        1
        )
      
    
    {\displaystyle A(n)\Rightarrow A(n+1)}
  
 für 
  
    
      
        n
        =
        1
        ,
        2
        ,
        3
        ,
        …
      
    
    {\displaystyle n=1,2,3,\ldots }
  
 (jeder Stein stößt beim Umfallen den nächsten Stein mit um).


## Beispiele
### Gaußsche Summenformel
Die Gaußsche Summenformel besagt: Für alle natürlichen Zahlen 
  
    
      
        n
        ≥
        1
      
    
    {\displaystyle n\geq 1}
  
 gilt

  
    
      
        1
        +
        2
        +
        ⋯
        +
        n
        =
        
          
            
              n
              (
              n
              +
              1
              )
            
            2
          
        
      
    
    {\displaystyle 1+2+\cdots +n={\frac {n(n+1)}{2}}}
  
.
Der Induktionsanfang ergibt sich unmittelbar:

  
    
      
        1
        =
        
          
            
              1
              (
              1
              +
              1
              )
            
            2
          
        
      
    
    {\displaystyle 1={\frac {1(1+1)}{2}}}
  

Im Induktionsschritt ist zu zeigen, dass für 
  
    
      
        n
        ≥
        1
      
    
    {\displaystyle n\geq 1}
  
 aus der Induktionsvoraussetzung

  
    
      
        1
        +
        2
        +
        ⋯
        +
        n
        =
        
          
            
              n
              (
              n
              +
              1
              )
            
            2
          
        
      
    
    {\displaystyle 1+2+\cdots +n={\frac {n(n+1)}{2}}}
  

die Induktionsbehauptung

  
    
      
        1
        +
        2
        +
        ⋯
        +
        n
        +
        (
        n
        +
        1
        )
        =
        
          
            
              (
              n
              +
              1
              )
              (
              (
              n
              +
              1
              )
              +
              1
              )
            
            2
          
        
      
    
    {\displaystyle 1+2+\cdots +n+(n+1)={\frac {(n+1)((n+1)+1)}{2}}}
  

(mit 
  
    
      
        (
        n
        
        +
        
        1
        )
      
    
    {\displaystyle (n\!+\!1)}
  
 an der Stelle des 
  
    
      
        n
      
    
    {\displaystyle n}
  
 der Induktionsvoraussetzung) folgt.
Dies gelingt, indem man die linke Seite der Induktionsbehauptung zunächst mithilfe der Induktionsvoraussetzung umformt und dann elementare Termumformungen vornimmt:

  
    
      
        
          
            
              
                1
                +
                2
                +
                ⋯
                +
                n
                +
                (
                n
                +
                1
                )
              
              
                
                =
                
                  
                    
                      n
                      (
                      n
                      +
                      1
                      )
                    
                    2
                  
                
                +
                (
                n
                +
                1
                )
              
            
            
              
              
                
                =
                
                  
                    
                      n
                      (
                      n
                      +
                      1
                      )
                      +
                      2
                      (
                      n
                      +
                      1
                      )
                    
                    2
                  
                
              
            
            
              
              
                
                =
                
                  
                    
                      (
                      n
                      +
                      1
                      )
                      (
                      n
                      +
                      2
                      )
                    
                    2
                  
                
              
            
            
              
              
                
                =
                
                  
                    
                      (
                      n
                      +
                      1
                      )
                      (
                      (
                      n
                      +
                      1
                      )
                      +
                      1
                      )
                    
                    2
                  
                
                .
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}1+2+\cdots +n+(n+1)&={\frac {n(n+1)}{2}}+(n+1)\\&={\frac {n(n+1)+2(n+1)}{2}}\\&={\frac {(n+1)(n+2)}{2}}\\&={\frac {(n+1)((n+1)+1)}{2}}.\end{aligned}}}
  

Mit dem Induktionsprinzip folgt die Gültigkeit der Gaußschen Summenformel für alle 
  
    
      
        n
        ≥
        1
      
    
    {\displaystyle n\geq 1}
  
.


### Summe ungerader Zahlen (Maurolicus 1575)
Die schrittweise Berechnung der Summe der ersten 
  
    
      
        n
      
    
    {\displaystyle n}
  
 ungeraden Zahlen,

  
    
      
        1
        =
        1
      
    
    {\displaystyle 1=1}
  

  
    
      
        1
        +
        3
        =
        4
      
    
    {\displaystyle 1+3=4}
  

  
    
      
        1
        +
        3
        +
        5
        =
        9
      
    
    {\displaystyle 1+3+5=9}
  

  
    
      
        1
        +
        3
        +
        5
        +
        7
        =
        16
      
    
    {\displaystyle 1+3+5+7=16}
  
,
legt die Vermutung nahe: Die Summe aller ungeraden Zahlen von 
  
    
      
        1
      
    
    {\displaystyle 1}
  
 bis 
  
    
      
        2
        n
        −
        1
      
    
    {\displaystyle 2n-1}
  
 ist gleich dem Quadrat von 
  
    
      
        n
      
    
    {\displaystyle n}
  
:

  
    
      
        1
        +
        3
        +
        5
        +
        ⋯
        +
        (
        2
        n
        −
        1
        )
        =
        
          n
          
            2
          
        
      
    
    {\displaystyle 1+3+5+\cdots +(2n-1)=n^{2}}
  
.
Sie wurde 1575 von Franciscus Maurolicus mit vollständiger Induktion bewiesen. Ein Beweis mit moderner Notation liest sich folgendermaßen:
Der Induktionsanfang mit 
  
    
      
        n
        =
        1
      
    
    {\displaystyle n=1}
  
 gilt wegen 
  
    
      
        1
        =
        
          1
          
            2
          
        
      
    
    {\displaystyle 1=1^{2}}
  
.
Im Induktionsschritt ist zu zeigen, dass aus der Induktionsvoraussetzung

  
    
      
        
          1
          +
          3
          +
          5
          +
          ⋯
          +
          (
          2
          n
          −
          1
          )
          =
          
            n
            
              2
            
          
        
      
    
    {\displaystyle \textstyle 1+3+5+\cdots +(2n-1)=n^{2}}
  
 für ein 
  
    
      
        n
        ≥
        1
      
    
    {\displaystyle n\geq 1}
  

die Induktionsbehauptung

  
    
      
        
          1
          +
          3
          +
          5
          +
          ⋯
          +
          (
          2
          (
          n
          +
          1
          )
          −
          1
          )
          =
          (
          n
          +
          1
          
            )
            
              2
            
          
        
      
    
    {\displaystyle \textstyle 1+3+5+\cdots +(2(n+1)-1)=(n+1)^{2}}
  

folgt. Er ergibt sich über folgende Gleichungskette, bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird:

  
    
      
        
          
            
              
                1
                +
                3
                +
                5
                +
                ⋯
                +
                (
                2
                (
                n
                +
                1
                )
                −
                1
                )
              
              
                
                =
                1
                +
                3
                +
                5
                +
                ⋯
                +
                (
                2
                n
                −
                1
                )
                +
                (
                2
                (
                n
                +
                1
                )
                −
                1
                )
              
            
            
              
              
                
                =
                
                  n
                  
                    2
                  
                
                +
                2
                n
                +
                1
              
            
            
              
              
                
                =
                (
                n
                +
                1
                
                  )
                  
                    2
                  
                
                .
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}1+3+5+\cdots +(2(n+1)-1)&=1+3+5+\cdots +(2n-1)+(2(n+1)-1)\\&=n^{2}+2n+1\\&=(n+1)^{2}.\end{aligned}}}
  

Mit dem Induktionsprinzip folgt die Gültigkeit der Aussage für alle 
  
    
      
        n
        ≥
        1
      
    
    {\displaystyle n\geq 1}
  
.


### Bernoullische Ungleichung
Nach der Bernoullische Ungleichung gilt für alle reellen Zahlen 
  
    
      
        x
        ≥
        −
        1
      
    
    {\displaystyle x\geq -1}
  
 und alle natürlichen Zahlen 
  
    
      
        n
        ≥
        0
      
    
    {\displaystyle n\geq 0}
  
 die Ungleichung

  
    
      
        (
        1
        +
        x
        
          )
          
            n
          
        
        ≥
        1
        +
        n
        x
      
    
    {\displaystyle (1+x)^{n}\geq 1+nx}
  
.
Der Induktionsanfang mit 
  
    
      
        n
        =
        0
      
    
    {\displaystyle n=0}
  
 gilt wegen 
  
    
      
        (
        1
        +
        x
        
          )
          
            0
          
        
        =
        1
        ≥
        1
      
    
    {\displaystyle (1+x)^{0}=1\geq 1}
  
.
Den Induktionsschritt gewinnt man über folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung verwendet, wobei die Bedingung 
  
    
      
        x
        ≥
        −
        1
      
    
    {\displaystyle x\geq -1}
  
 dafür sorgt, dass der Term nicht negativ wird:

  
    
      
        
          
            
              
                (
                1
                +
                x
                
                  )
                  
                    n
                    +
                    1
                  
                
              
              
                
                =
                
                  (
                  1
                  +
                  x
                  
                    )
                    
                      n
                    
                  
                
                ⋅
                (
                1
                +
                x
                )
              
            
            
              
              
                
                ≥
                (
                1
                +
                n
                x
                )
                ⋅
                (
                1
                +
                x
                )
              
            
            
              
              
                
                =
                1
                +
                x
                +
                n
                x
                +
                n
                
                  x
                  
                    2
                  
                
              
            
            
              
              
                
                ≥
                1
                +
                x
                +
                n
                x
              
            
            
              
              
                
                =
                1
                +
                (
                n
                +
                1
                )
                x
                .
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}(1+x)^{n+1}&={(1+x)^{n}}\cdot (1+x)\\&\geq (1+nx)\cdot (1+x)\\&=1+x+nx+nx^{2}\\&\geq 1+x+nx\\&=1+(n+1)x.\end{aligned}}}
  

Nach dem Induktionsprinzip gilt die Behauptung für alle 
  
    
      
        n
        ∈
        
          
            N
          
          
            0
          
        
      
    
    {\displaystyle n\in \mathbb {N} _{0}}
  
.


### Pferde-Paradox
Das Pferde-Paradox ist ein Standardbeispiel für eine fehlerhafte Anwendung der vollständigen Induktion und illustriert die Bedeutung des Zusammenspiels von Induktionsverankerung und Induktionsschritt. Bei ihm wird die unsinnige Aussage, dass in einer Herde von 
  
    
      
        n
      
    
    {\displaystyle n}
  
 Pferden alle immer die gleiche Farbe besitzen, anhand einer scheinbar korrekten Induktion bewiesen. Dabei ist der Induktionsschritt selbst korrekt, würde aber die Induktionsverankerung bei einem 
  
    
      
        n
        ≥
        2
      
    
    {\displaystyle n\geq 2}
  
 benötigen, während der (fehlerhafte) Beweis die Induktion bei 
  
    
      
        n
        =
        1
      
    
    {\displaystyle n=1}
  
 verankert und somit schon der Schritt von 
  
    
      
        n
        =
        1
      
    
    {\displaystyle n=1}
  
 auf 
  
    
      
        n
        =
        2
      
    
    {\displaystyle n=2}
  
 scheitert.


## Etymologie und Geschichte
Die Bezeichnung Induktion leitet sich ab von lat. inductio, wörtlich „Hineinführung“. Der Zusatz vollständig signalisiert, dass es sich hier im Gegensatz zur Induktion im Sinne der Philosophie, die aus Spezialfällen ein allgemeines Gesetz erschließt und kein exaktes Schlussverfahren ist, um ein deduktives Beweisverfahren handelt.
Das Induktionsprinzip steckt latent bereits in der von Euklid überlieferten pythagoreischen Zahlendefinition: „Zahl ist die aus Einheiten zusammengesetzte Menge.“ Euklid führte aber noch keine Induktionsbeweise, sondern begnügte sich mit intuitiven, exemplarischen Induktionen, die sich aber vervollständigen lassen. Auch andere bedeutende Mathematiker der Antike und des Mittelalters hatten noch kein Bedürfnis nach präzisen Induktionsbeweisen. Vereinzelte Ausnahmen im hebräischen und arabischen Sprachraum blieben ohne Nachfolge.
Lange galt ein Beweis von Franciscus Maurolicus von 1575 als älteste explizite vollständige Induktion (unten ausgeführt). Er erörterte aber das allgemeine Beweisverfahren noch nicht. Erst Blaise Pascal thematisierte das Induktionsprinzip mit Induktionsanfang und Induktionsschritt in seinem Traité du triangle arithmétique von 1654. Zur Verbreitung von Induktionsbeweisen trug ab 1686 Jakob I Bernoulli wesentlich bei.
Das Beweisverfahren wurde dann 1838 von Augustus De Morgan erstmals als Induktion oder sukzessive Induktion bezeichnet. 1888 prägte schließlich Richard Dedekind in seiner Schrift Was sind und was sollen die Zahlen? den Begriff vollständige Induktion. Über dieses Werk aus der Gründerzeit der Mengenlehre wurde sie zum allgemein bekannten, etablierten Beweisprinzip, auf das seither kein Zweig der Mathematik mehr verzichten kann. Ein Jahr später, 1889, formulierte Giuseppe Peano mit den Peanoschen Axiomen den ersten formalisierten Kalkül für die natürlichen Zahlen mit einem Induktionsaxiom, aus dem sich das Beweisschema der vollständigen Induktion herleiten lässt. Er zeigte mit formaler Strenge, dass aus seinen Zahlaxiomen, zu denen das Induktionsaxiom gehört, die ganze Arithmetik bis hin zu den reellen Zahlen ableitbar ist. Dadurch machte er die fundamentale Bedeutung und die Leistungskraft der Induktion voll bewusst.


## Prinzip der vollständigen Induktion
Das Beweisverfahren der vollständigen Induktion beruht auf dem Prinzip der vollständigen Induktion:

Ist 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 eine Aussage über natürliche Zahlen, so dass

  
    
      
        A
        (
        0
        )
      
    
    {\displaystyle A(0)}
  
 bzw. 
  
    
      
        A
        (
        1
        )
      
    
    {\displaystyle A(1)}
  
 gilt und
für alle 
  
    
      
        n
      
    
    {\displaystyle n}
  
 die Gültigkeit von 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 die Gültigkeit von 
  
    
      
        A
        (
        n
        +
        1
        )
      
    
    {\displaystyle A(n+1)}
  
 nach sich zieht,
so gilt die Aussage für jede natürliche Zahl.
Als formale Schlussregel mit dem Ableitungsoperator 
  
    
      
        ⊢
      
    
    {\displaystyle \vdash }
  
 lautet das Prinzip der vollständigen Induktion:

  
    
      
        A
        (
        0
        )
        ∧
        ∀
        n
        ∈
        
          N
        
        :
        (
        A
        (
        n
        )
        ⇒
        A
        (
        n
        +
        1
        )
        )
         
        ⊢
         
        ∀
        n
        ∈
        
          N
        
        :
        A
        (
        n
        )
      
    
    {\displaystyle A(0)\land \forall n\in \mathbb {N} \colon (A(n)\Rightarrow A(n+1))\ \vdash \ \forall n\in \mathbb {N} \colon A(n)}
  


### Logische Stellung des Induktionsprinzips
Das Induktionsprinzip kann entweder als Axiom gesetzt oder aus anderen Axiomen hergeleitet werden. Im Rahmen der Arithmetik und Zahlentheorie wird es meist aus dem gleichwertigen fünften Peano-Axiom, dem Induktionsaxiom, hergeleitet. Dieses lautet:

Ist 
  
    
      
        
        K
      
    
    {\displaystyle \,K}
  
 eine Teilmenge der natürlichen Zahlen 
  
    
      
        
          N
        
      
    
    {\displaystyle \mathbb {N} }
  
 mit den Eigenschaften:

  
    
      
        
        1
      
    
    {\displaystyle \,1}
  
 ist ein Element von 
  
    
      
        
        K
      
    
    {\displaystyle \,K}
  

Mit 
  
    
      
        
        n
      
    
    {\displaystyle \,n}
  
 aus 
  
    
      
        
        K
      
    
    {\displaystyle \,K}
  
 ist stets auch 
  
    
      
        
        n
        +
        1
      
    
    {\displaystyle \,n+1}
  
 aus 
  
    
      
        
        K
      
    
    {\displaystyle \,K}
  
,
dann ist 
  
    
      
        
        K
        =
        
          N
        
      
    
    {\displaystyle \,K=\mathbb {N} }
  
.
Auch in anderen Konzepten der natürlichen Zahlen sind die Peano-Axiome und damit auch das Prinzip der vollständigen Induktion herleitbar, zum Beispiel bei der Definition der natürlichen Zahlen

als von 1 erzeugte geordnete Halbgruppe, die der zitierten pythagoreischen Zahlendefinition entspricht;
als frei von 1 erzeugtes Monoid, das von der Addition der Zahlen ausgeht;
als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht;
als kleinste induktive Menge, nämlich als kleinste Menge, die das Unendlichkeitsaxiom erfüllt, wie es in der Mengenlehre üblich ist;
als Klasse der endlichen Ordinalzahlen, die nur eine allgemeine Mengenlehre ohne Unendlichkeitsaxiom voraussetzt.


## Induktionsvarianten
### Induktion mit beliebigem Anfang
Möchte man zeigen, dass eine Aussage 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 nicht für alle natürlichen Zahlen, sondern nur für natürliche Zahlen größer oder gleich einer Zahl 
  
    
      
        
          n
          
            0
          
        
      
    
    {\displaystyle n_{0}}
  
 gilt, so besteht ein Induktionsbeweis aus den beiden folgenden Schritten:

Im Induktionsanfang zeigt man, dass die Aussage für 
  
    
      
        
          n
          
            0
          
        
      
    
    {\displaystyle n_{0}}
  
 gilt.
Im Induktionsschritt zeigt man, dass für beliebiges 
  
    
      
        n
        ≥
        
          n
          
            0
          
        
      
    
    {\displaystyle n\geq n_{0}}
  
 gilt: Ist die Aussage für 
  
    
      
        n
      
    
    {\displaystyle n}
  
 richtig, so auch für 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
  
.


#### Beispiel
Induktionsbeweis der Ungleichung 
  
    
      
        
          2
          
            n
          
        
        ≥
        
          n
          
            2
          
        
      
    
    {\displaystyle 2^{n}\geq n^{2}}
  
 für natürliche Zahlen 
  
    
      
        n
        ≥
        4
      
    
    {\displaystyle n\geq 4}
  
:
Induktionsanfang: Für 
  
    
      
        
        n
        =
        4
      
    
    {\displaystyle \,n=4}
  
 ist die Ungleichung wegen 
  
    
      
        
          2
          
            4
          
        
        =
        16
        ≥
        16
        =
        
          4
          
            2
          
        
      
    
    {\displaystyle 2^{4}=16\geq 16=4^{2}}
  
 erfüllt.
Induktionsschritt: Für ein 
  
    
      
        n
        ≥
        4
      
    
    {\displaystyle n\geq 4}
  
 gelte 
  
    
      
        
          2
          
            n
          
        
        ≥
        
          n
          
            2
          
        
      
    
    {\displaystyle 2^{n}\geq n^{2}}
  
 (Induktionsvoraussetzung). Damit erhält man die Abschätzung

  
    
      
        
          
            
              
                
                  2
                  
                    n
                    +
                    1
                  
                
              
              
                =
                2
                ⋅
                
                  2
                  
                    n
                  
                
                ≥
                2
                ⋅
                
                  n
                  
                    2
                  
                
              
              
                =
                
                  n
                  
                    2
                  
                
                +
                n
                ⋅
                n
                ≥
                
                  n
                  
                    2
                  
                
                +
                4
                n
              
            
            
              
              
                =
                
                  n
                  
                    2
                  
                
                +
                2
                n
                +
                2
                n
              
              
                ≥
                
                  n
                  
                    2
                  
                
                +
                2
                n
                +
                2
                ⋅
                4
              
            
            
              
              
                ≥
                
                  n
                  
                    2
                  
                
                +
                2
                n
                +
                1
              
              
                =
                (
                n
                +
                1
                
                  )
                  
                    2
                  
                
                .
              
            
          
        
      
    
    {\displaystyle {\begin{array}{lll}2^{n+1}&=2\cdot 2^{n}\geq 2\cdot n^{2}&=n^{2}+n\cdot n\geq n^{2}+4n\\&=n^{2}+2n+2n&\geq n^{2}+2n+2\cdot 4\\&\geq n^{2}+2n+1&=(n+1)^{2}.\end{array}}}
  

Dabei wurde die Induktionsvoraussetzung im zweiten Schritt verwendet und im vierten und sechsten Schritt die Voraussetzung 
  
    
      
        n
        ≥
        4
      
    
    {\displaystyle n\geq 4}
  
.
Die endlich vielen Fälle, die solch ein allgemeinerer Induktionsbeweis nicht abdeckt, können einzeln untersucht werden. Im Beispiel ist die Ungleichung für 
  
    
      
        n
        =
        3
      
    
    {\displaystyle n=3}
  
 offenbar falsch.


### Induktion mit mehreren Vorgängern
In manchen Induktionsbeweisen kommt man in der Induktionsvoraussetzung mit dem Bezug auf einen einzigen Vorgänger nicht aus, bspw. wenn eine Rekursionsformel mehrere Vorgänger enthält.
Der Induktionsanfang ist dann für mehrere Startwerte durchzuführen.
Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung für 
  
    
      
        n
      
    
    {\displaystyle n}
  
 und 
  
    
      
        n
        −
        1
      
    
    {\displaystyle n-1}
  
 nötig, dann ist ein Induktionsanfang für zwei aufeinander folgende Zahlen, also etwa 0 und 1, erforderlich.


### Starke Induktion
Die starke Induktion beruht auf dem Prinzip der starken Induktion, das Folgendes besagt:

Zieht für jedes 
  
    
      
        k
      
    
    {\displaystyle k}
  
 die Gültigkeit der Aussagen 
  
    
      
        A
        (
        1
        )
        ,
        A
        (
        2
        )
        ,
        …
        ,
        A
        (
        k
        −
        1
        )
      
    
    {\displaystyle A(1),A(2),\ldots ,A(k-1)}
  
 die Gültigkeit von 
  
    
      
        A
        (
        k
        )
      
    
    {\displaystyle A(k)}
  
 nach sich, so gilt 
  
    
      
        A
        (
        n
        )
      
    
    {\displaystyle A(n)}
  
 für alle natürlichen Zahlen.
Bei einem Beweis mittels starker Induktion ist folglich nur der Induktionsschritt zu zeigen. Hierzu setzt man voraus, dass für beliebiges 
  
    
      
        k
      
    
    {\displaystyle k}
  
 die Aussage 
  
    
      
        A
        (
        1
        )
        ,
        A
        (
        2
        )
        ,
        …
        ,
        A
        (
        k
        −
        1
        )
      
    
    {\displaystyle A(1),A(2),\ldots ,A(k-1)}
  
 gelten (starke Induktionsvoraussetzung), und zeigt dann die Gültigkeit von 
  
    
      
        A
        (
        k
        )
      
    
    {\displaystyle A(k)}
  
 (Induktionsbehauptung).
Das Prinzip der „gewöhnlichen“ Induktion ist äquivalent zum Prinzip der starken Induktion, das heißt beide Prinzipien lassen sich jeweils aus dem anderen folgern. Trotz dieser prinzipiellen Gleichwertigkeit in der Beweisstärke ist der Unterschied in der Ausdrucksstärke wegen der beliebig vielen Startwerte und der Möglichkeit des Rückgriffs auf beliebig viele Vorgänger groß, besonders bei rekursiven Definitionen.


#### Beispiel
Ein Beispiel ist der Beweis, dass jede natürliche Zahl 
  
    
      
        n
        ≥
        2
      
    
    {\displaystyle n\geq 2}
  
 einen Primzahl-Teiler hat:
Die Aussage sei für alle 
  
    
      
        m
      
    
    {\displaystyle m}
  
 mit 
  
    
      
        2
        ≤
        m
        ≤
        n
      
    
    {\displaystyle 2\leq m\leq n}
  
 erfüllt. Ist nun 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
  
 eine Primzahl, so ist 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
  
 selbst der gesuchte Teiler, und die Behauptung ist bewiesen. Ist 
  
    
      
        
        n
        +
        1
      
    
    {\displaystyle \,n+1}
  
 keine Primzahl, so gibt es zwei Zahlen 
  
    
      
        a
        ,
        b
        ∈
        
          N
        
      
    
    {\displaystyle a,b\in \mathbb {N} }
  
 mit 
  
    
      
        a
        ⋅
        b
        =
        n
        +
        1
      
    
    {\displaystyle a\cdot b=n+1}
  
 und 
  
    
      
        1
        <
        a
        <
        n
        +
        1
      
    
    {\displaystyle 1<a<n+1}
  
. In diesem Fall besitzt 
  
    
      
        a
      
    
    {\displaystyle a}
  
 gemäß Induktionsvoraussetzung einen Primzahl-Teiler, etwa 
  
    
      
        p
      
    
    {\displaystyle p}
  
. Dann teilt 
  
    
      
        p
      
    
    {\displaystyle p}
  
 auch 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
  
 und ist Primzahl-Teiler von 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
  
. Damit ist auch für diesen zweiten Fall die Behauptung bewiesen.


### Induktion mit Vorwärts-Rückwärts-Schritten
Augustin-Louis Cauchy führte 1821 eine Induktionsvariante vor, bei der der vorwärts gerichtete Induktionsschritt Sprünge macht (nämlich von 
  
    
      
        
          2
          
            k
          
        
      
    
    {\displaystyle 2^{k}}
  
 nach 
  
    
      
        
          2
          
            k
            +
            1
          
        
      
    
    {\displaystyle 2^{k+1}}
  
) und die entstandenen Lücken nachträglich durch eine rückwärts gerichtete Herleitung von 
  
    
      
        
          2
          
            k
          
        
      
    
    {\displaystyle 2^{k}}
  
 nach 
  
    
      
        n
        <
        
          2
          
            k
          
        
      
    
    {\displaystyle n<2^{k}}
  
 auf einen Schlag gefüllt werden. Mit dieser Variante bewies er die Ungleichung vom arithmetischen und geometrischen Mittel.


### Weitere Induktionsvarianten
Es gibt auch Sachlagen, bei denen Aussagen über alle ganzen Zahlen (positive und negative) mit vollständiger Induktion bewiesen werden können. Der Beweis in die positive Richtung geschieht wie gewohnt mit einem beliebigen Induktionsanfang und dem positiven Induktionsschritt von 
  
    
      
        n
      
    
    {\displaystyle n}
  
 nach 
  
    
      
        n
        +
        1
      
    
    {\displaystyle n+1}
  
. Danach kann es möglich sein, den Induktionsschritt in die negative Richtung von 
  
    
      
        n
      
    
    {\displaystyle n}
  
 nach 
  
    
      
        n
        −
        1
      
    
    {\displaystyle n-1}
  
 auszuführen. Beispielsweise lässt sich bei der Fibonacci-Folge die Rekursionsgleichung in die Gegenrichtung umstülpen.
Die vollständige Induktion lässt sich auf Ordinalzahlen verallgemeinern. Bei Ordinalzahlen, die größer als die natürlichen Zahlen sind, spricht man dann von transfiniter Induktion.
Die Induktion lässt sich auch übertragen auf sogenannte fundierte Mengen, die eine der Zahlenordnung vergleichbare Ordnungsstruktur aufweisen; hier spricht man zuweilen von struktureller Induktion.


## Rekursive oder induktive Definition
Die rekursive Definition – auch induktive Definition genannt – ist ein der vollständigen Induktion analoges Verfahren, bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird. Dadurch ist der Term schon für alle natürlichen Zahlen erklärt.


### Beispiel
Die Potenzen einer Zahl 
  
    
      
        x
      
    
    {\displaystyle x}
  
 sind erklärt durch

  
    
      
        
          x
          
            1
          
        
        :=
        x
      
    
    {\displaystyle x^{1}:=x}
  
 und
die Rekursionsformel 
  
    
      
        
          x
          
            n
            +
            1
          
        
        :=
        
          x
          
            n
          
        
        ⋅
        x
      
    
    {\displaystyle x^{n+1}:=x^{n}\cdot x}
  


## Anmerkungen
## Literatur
Otto Forster, Florian Lindemann: Analysis 1. 13. Auflage. Springer Spektrum, Wiesbaden 2023, ISBN 978-3-658-40129-0, S. 1–24.
Konrad Königsberger: Analysis 1. 6. Auflage. Springer, Berlin 2004, ISBN 978-3-540-40371-5, S. 1–2.
Gerhard Schurz: Logik: Grund- und Aufbaukurs in Aussagen- und Prädikatenlogik. 2. Auflage. De Gruyter, Berlin / Boston 2020, ISBN 978-3-11-069714-8, S. 357–360.
Florian André Dalwigk: Vollständige Induktion. Springer, Berlin / Heidelberg 2019, ISBN 978-3-662-58632-7
Felix Göbler, Alex Küronya: Vollständige Induktion. In: Einstieg in die beweisorientierte Mathematik. Springer, Berlin / Heidelberg 2023, ISBN 978-3-662-66355-4, S. 95–109, doi:10.1007/978-3-662-66356-1_5. 
Ilja S. Sominski: Die Methode der vollständigen Induktion (= Kleine Ergänzungsreihe zu den Hochschulbüchern Mathematik. Band 3). 10. Auflage. VEB Deutscher Verlag der Wissenschaften, Berlin 1971.
David S. Gunderson: Handbook of Mathematical Induction. Taylor & Francis, 2010, ISBN 978-1-4200-9365-0.


## Weblinks
Vollständige Induktion mit Beispielen.
Vollständige Induktion. henked.de
emath.de (PDF; 837 kB) Umfangreiche Aufgabensammlung zur vollständigen Induktion
Joachim Mohr: Crashkurs in die vollständige Induktion. kilchb.de
Christian Spannagel: Vorlesungen zur vollständigen Induktion.
Beweise mit vollständiger Induktion auf Video anschaulich erklärt:
Summe ungerader Zahlen (Satz des Maurolicus) auf YouTube.
Gaußsche Summenformel auf YouTube.
Bernoulli-Ungleichung auf YouTube.
Beweis von 2n≥n2 auf YouTube.


## Einzelnachweise