Vollständige Induktion
Welche zwei Schritte umfasst ein Beweis durch vollständige Induktion?
Erklärung: Vollständige Induktion besteht aus: (1) Zeige die Aussage fßr n = 1 (Induktionsanfang), (2) Zeige: wenn sie fßr n gilt, dann auch fßr n+1 (Induktionsschritt).
Beim Induktionsschritt nimmt man an, dass die Aussage fĂźr ein festes n gilt (Induktionsvoraussetzung).
Erklärung: Richtig. Die Induktionsvoraussetzung (IV) ist die Annahme, dass die Aussage fßr n wahr ist. Daraus wird die Gßltigkeit fßr n+1 gefolgert.
Induktionsanfang fßr die Formel 1 + 2 + ⌠+ n = n(n+1)/2: Fßr n = 1 ist die linke Seite 1, die rechte Seite 1¡2/2 = ___.
Erklärung: 1¡2/2 = 1. Beide Seiten stimmen ßberein, der Induktionsanfang ist bestätigt.
Beweise per Induktion: 1 + 3 + 5 + ⌠+ (2nâ1) = n². PrĂźfe den Induktionsanfang fĂźr n = 1: Was ist (2¡1â1)?
Erklärung: 2¡1 â 1 = 1 und 1² = 1. â
Im Induktionsschritt fßr 1 + 2 + ⌠+ n = n(n+1)/2 addiert man zum Term fßr n das Glied (n+1). Was ergibt n(n+1)/2 + (n+1)?
Erklärung: n(n+1)/2 + (n+1) = (n+1)¡[n/2 + 1] = (n+1)¡(n+2)/2. Das ist die Formel fßr n+1.
Vollständige Induktion kann nur fßr Summenformeln verwendet werden.
Erklärung: Falsch. Induktion kann fßr beliebige Aussagen ßber natßrliche Zahlen verwendet werden: Summenformeln, Ungleichungen, Teilbarkeit, etc.
Die Formel 1² + 2² + ⌠+ n² = n(n+1)(2n+1)/6. Berechne die rechte Seite fßr n = 4.
Erklärung: 4¡5¡9/6 = 180/6 = 30. Probe: 1+4+9+16 = 30. â
Im Induktionsschritt geht man von der Annahme A(n) zur Behauptung A(___) Ăźber.
Erklärung: Man zeigt: A(n) wahr ⚠A(n+1) wahr.
n² + n + 41 ergibt fĂźr n = 1, 2, âŚ, 39 lauter Primzahlen. Was ergibt sich fĂźr n = 40?
Erklärung: 40² + 40 + 41 = 1600 + 40 + 41 = 1681 = 41 ¡ 41 â keine Primzahl. (1721 entsteht durch einen Rechenfehler: 40 doppelt addiert.) Endlich viele Beispiele beweisen keine allgemeine Aussage â das Muster bricht genau hier. Deshalb braucht man einen Beweis fĂźr alle n, etwa durch vollständige Induktion.
Beweise: 2âż > n fĂźr alle n ⼠1. Im Induktionsschritt: Wenn 2âż > n, dann 2âżâşÂš = 2¡2âż > 2n. Ist 2n > n+1 fĂźr n ⼠1? Ab welchem n gilt 2n ⼠n+1?
Erklärung: 2n ⼠n+1 âş n ⼠1. Also gilt 2n > n+1 fĂźr n ⼠1 (sogar 2n ⼠n+1, mit Gleichheit bei n=1). Zusammen: 2âżâşÂš > n+1.
Wenn der Induktionsanfang fehlt, ist der Beweis durch vollständige Induktion ungßltig.
Erklärung: Richtig. Ohne Induktionsanfang hat man keinen Ausgangspunkt. Beide Teile sind notwendig.
Die Formel 1 + 3 + 5 + ⌠+ (2nâ1) = n² beschreibt die Summe der ersten n ___ Zahlen.
Erklärung: Die Folge 1, 3, 5, 7, ⌠besteht aus den ungeraden natßrlichen Zahlen.
Induktionsbeweis: Zeige n! > 2⿠fßr n ⼠4. Prßfe den Induktionsanfang: Berechne 4!.
Erklärung: 4! = 24 > 2â´ = 16. â
Im Induktionsschritt fßr 1³ + 2³ + ⌠+ n³ = [n(n+1)/2]² wird (n+1)³ addiert. Das Ergebnis soll [(n+1)(n+2)/2]² ergeben. Welche Zwischenform entsteht?
Erklärung: Man klammert (n+1)² aus und zeigt, dass n²/4 + (n+1) = (n² + 4n + 4)/4 = (n+2)²/4.
Berechne 1³ + 2³ + 3³ + 4³ nach der Formel [n(n+1)/2]².
Erklärung: [4¡5/2]² = [10]² = 100. Probe: 1 + 8 + 27 + 64 = 100. â
Die Induktionsvoraussetzung darf beim Induktionsschritt NICHT verwendet werden.
Erklärung: Falsch. Die Induktionsvoraussetzung MUSS im Induktionsschritt verwendet werden â sie ist die Annahme, von der aus man folgert.
Welche Aussage lässt sich NICHT durch vollständige Induktion beweisen?
Erklärung: Vollständige Induktion beweist Aussagen Ăźber natĂźrliche Zahlen. Die Irrationalität von â2 ist keine Aussage Ăźber alle n â â.
Die Summe 1/1¡2 + 1/2¡3 + ⌠+ 1/n¡(n+1) = n/(n+1). ĂberprĂźfe fĂźr n = 3: Berechne 1/2 + 1/6 + 1/12 als Bruch. Gib den Zähler an, wenn der Nenner 12 ist.
Erklärung: 1/2 + 1/6 + 1/12 = 6/12 + 2/12 + 1/12 = 9/12 = 3/4 = n/(n+1). â
Der Induktionsanfang fĂźr die Teilbarkeitsaussage '6 | (nÂł â n) fĂźr alle n ⼠1' ergibt fĂźr n = 1: 1Âł â 1 = ___.
Erklärung: 1Âł â 1 = 0, und 0 ist durch 6 teilbar. â
Man kann den Induktionsanfang auch bei n = 0 oder einem anderen Startwert nâ beginnen.
Erklärung: Richtig. Die Induktion muss nicht bei n = 1 starten. Der Startwert hängt davon ab, ab welchem n die Aussage gelten soll.