Vollständige Induktion
Wann kann man vollständige Induktion anwenden?
Immer, wenn verlangt wird, zu zeigen, daß eine rekursive Definition einer direkten gleich ist. Dabei sind rekursive Definitionen solche, bei denen man F(n) aus F(k) mit k<n berechnet, während eine direkte Definition eine Berechnung von F(n) ohne Rückgriff auf F möglich macht.
Beispiel für eine rekursive Definition sind z.B. die Fibonacci-Zahlen:
F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2)
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| F(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
Wie geht man bei einer vollständigen Induktion vor?
| Die Vorgehensweise | Das Beispiel |
|
F(0)=0 F(n)=F(n-1)+2 F(n) soll das Gleiche wie G(n)=2n sein. |
1. Schritt: Der Basisfall
| Zeige, daß F(n)=G(N) für den niedrigsten Fall, ab dem F(n)=G(n) gelten soll. | F(0)=0 (s. Definition von F(n)) G(n)=2* 0=0=F(0) |
2. Schritt: Bis kurz vor die Induktion
| Beginne mit der rekursiven Definition von F. Löse diese Definition so weit auf, daß nur noch Aufrufe von F auf der rechten Seite stehen, deren Funktionswert niedriger als n ist. |
F(n)=F(n-1)+2 war doch einfach, oder? |
3. Schritt: Die Induktion
| Ersetze nun alle dieser Aufrufe der rechten Seite durch die Gleichung G(x), wobei x der jeweilige Wert der F-Funktion ist. |
F(n)=F(n-1)+2 F(n)=G(n-1)+2 F(n)=2(n-1)+2 |
4. Schritt: Das Auflösen
| Löse nun die Gleichung so weit auf, daß du die Gleichung F(n)=dem Funktionswert von G(n) erhältst. Damit ist bewiesen, daß G(n)=F(n) ist. |
F(n)=2n-2+2 F(n)=2n qed |
Anmerkung: Stukturelle Induktion
Die Induktion funktioniert auch, wenn Gleichungen für z.B. Bäume bewiesen werden sollen. Ein Binärbaum besteht aus Knoten, von denen aus 2 weitere Knoten abweichen oder von denen keine weiteren Knoten ausgehen (dann wird der Knoten Blatt genannt).
Bsp.:
Kreise sind normale Knoten, Kästchen sind Blätter.
Für solche Binärbäume gilt folgende Bedingung: Anzahl der Knoten (AK
) =Anzahl Blätter (AB) - 1.
Der Beweis hierfür kann per Induktion geschehen. Wir brauchen also wieder einen Basisfall. Das wäre ein Baum, der keine Knoten, sondern nur Blätter hat => 0=AK=AB-1=1-1=0 ÿ
Wie gehen wir nun bei einem Baum mit n Knoten vor? Wir wählen einen Baum mit n-1 Knoten, dem genau dieser n-te Knoten fehlt. Für diesen dürfen wir annehmen, daß die Bedingung AK= AB-1 gilt. Wenn wir nun den fehlenden Knoten anhängen, so müssen wir dafür ein Blatt entfernen (an seine Position tritt ja der Knoten). Dafür kommen zwei neue Blätter sowie ein Knoten hinzu.
=> AK+1= AB-1+2-1
=> AK+1= AB
=> AK= AB-1