Assertion The power set P(M) of a set M with n elements contains 2n elements. Proof base case: n = 0 The set which contains 0 elements is the empty set . Its power set contains 1 element (1 = 20), namely the empty set: . Iinductive step: A(n) => A(n+1) Let be a set […]
Schlagwort: Vollständige Induktion
Wir beweisen die Existenz von Normalteilern in Gruppen einer bestimmten Ordnung. Behauptung Sei p eine Primzahl und G eine endliche Gruppe der Ordnung .Dann besitzt G einen Normalteiler der Ordnung pr-1. Beweis Wir beweisen diese Behauptung durch eine vollständige Induktion nach r. Induktionsanfang: r=1 $$\{e\}\triangleleft G$$ ist ein Normalteiler der Ordnung 1. Induktionsschritt: A(r-1) => […]
Behauptung Wir behaupten, dass sich die Gaußsche Summenformel auf folgende Weise schreiben lässt: Beweis Induktionsanfang: n = 1 Setzen wir für n die erste natürliche Zahl 1 ein, dann ist die Behauptung wahr:$$1 = \frac{2}{2} = \frac{1(1+1)}{2}$$ Induktionsschritt: A(n) => A(n+1) Angenommen, die Behauptung gilt für alle natürlichen Zahlen 1 … n. Dann soll sie […]
Die Potenzmenge ist die Menge aller Teilmengen einer gegebenen Grundmenge. Die Potenzmenge einer Menge enthält unter anderem immer die leere Menge und auch die Grundmenge selbst. Wir beweisen durch vollständige Induktion: Wenn die Grundmenge n Elemente hat, dann hat ihre Potenzmenge 2n Elemente. Behauptung Die Potenzmenge P(M) einer n-elementigen Menge M enthält genau 2n Elemente. […]
Kategorien
p teilt (n^p – n)
Behauptung Sei eine beliebige Primzahl. Dann gilt: für alle Dieser Beweis ist Grundlage für den kleinen Satz von Fermat. Beweis Induktionsanfang: n = 1 Für jede Primzahl gilt: Induktionsschritt: n => n+1 Angenommen, die Aussage ist richtig für alle natürlichen Zahlen bis n. Dann folgt daraus, dass die Aussage auch richtig ist für n+1: Der […]