Vollständige Induktion

Schreibe bei jeder Aufgabe deinen Lösungsweg auf.

1.
Welche zwei Teile muss jeder Beweis durch vollständige Induktion enthalten?
1. a)Nur das Prüfen der Fälle $n = 1$ bis $n = 5$
2. b)Ein Gegenbeispiel und einen Widerspruch
3. c)Einen Induktionsanfang und einen Induktionsschritt
4. d)Eine Tabelle mit Aussagen und Begründungen
Lösung: Einen Induktionsanfang und einen Induktionsschritt
Jeder Induktionsbeweis braucht einen Induktionsanfang (der erste Stein fällt) und einen Induktionsschritt (jeder fallende Stein wirft den nächsten um). Ein paar geprüfte Fälle sind kein Beweis, und Gegenbeispiele oder Tabellen gehören zu anderen Beweisarten.
2.
Die Formel $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ wurde mit Induktion bewiesen. Prüfe sie für $n = 5$ : Was ist $1 + 2 + 3 + 4 + 5$ ?
Lösung: 15
$1 + 2 + 3 + 4 + 5 = 15$ und $\dfrac{5 \cdot 6}{2} = 15$ . Die Formel liefert denselben Wert.
3.
Prüfe $1 + 3 + 5 + \dots + (2n-1) = n^2$ für $n = 6$ : Was ist $1 + 3 + 5 + 7 + 9 + 11$ ?
Lösung: 36
$1 + 3 + 5 + 7 + 9 + 11 = 36 = 6^2$ , genau wie die Formel vorhersagt.
4.
Was garantiert der Induktionsschritt im Dominobild der Induktion?
1. a)Alle Steine sind gleich groß
2. b)Der erste Stein fällt
3. c)Jeder fallende Stein wirft den nächsten um
4. d)Der letzte Stein fällt
Lösung: Jeder fallende Stein wirft den nächsten um
Der Induktionsschritt beweist $P(k) \Rightarrow P(k+1)$ : Immer wenn ein Stein fällt, fällt auch der nächste. Dass der erste Stein fällt, ist der Induktionsanfang. Einen letzten Stein gibt es nicht, die Reihe ist endlos.
5.
Bevor du $2^n > n$ beweist, prüfe die ersten Dominosteine: Berechne $2^n$ für $n = 1, 2, 3$ .
Lösung: 8
1. Was ist $2^1$ ? (Induktionsanfang, vergleiche mit $n = 1$ ) 2
2. Was ist $2^2$ ? (vergleiche mit $n = 2$ ) 4
3. Was ist $2^3$ ? (vergleiche mit $n = 3$ ) 8
6.
Prüfe die Formel $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ für $n = 3$ .
Lösung: 15
1. Berechne die linke Seite $1 + 2 + 4 + 8$ . 15
2. Berechne $2^{3+1} = 2^4$ . 16
3. Berechne die rechte Seite $2^4 - 1$ . 15
7.
Sei $P(n)$ die Aussage $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ . Im Induktionsschritt mit $k = 9$ ist die rechte Seite von $P(k+1)$ gleich $\dfrac{(k+1)(k+2)}{2}$ . Welchen Wert hat sie?
Lösung: 55
$\dfrac{10 \cdot 11}{2} = 55$ . Probe: Die Voraussetzung liefert $1 + \dots + 9 = 45$ , und mit dem nächsten Summanden $10$ erhält man $55$ .
8.
Benutze die mit Induktion bewiesene Formel $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ , um $1 + 2 + 4 + 8 + 16 + 32 + 64$ zu berechnen.
Lösung: 127
Der letzte Summand ist $2^6$ , also $n = 6$ , und die Summe ist $2^7 - 1 = 128 - 1 = 127$ .
9.
Welcher Summand wird im Induktionsschritt für $1 + 3 + 5 + \dots + (2n-1) = n^2$ zu $1 + 3 + \dots + (2k-1)$ addiert, um die linke Seite von $P(k+1)$ zu erhalten?
1. a) $2k + 1$
2. b) $k + 1$
3. c) $2k$
4. d) $2k - 1$
Lösung: $2k + 1$
Der letzte Summand von $P(k+1)$ ist $2(k+1) - 1 = 2k + 1$ . Der Summand $2k - 1$ ist schon in der Summe, und $k + 1$ und $2k$ sind keine ungeraden Zahlen dieses Musters.
10.
Vollziehe den Induktionsschritt für $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ mit Zahlen nach, mit $k = 4$ .
Lösung: 15
1. Laut Voraussetzung ist $1 + 2 + 3 + 4 = \dfrac{4 \cdot 5}{2}$ . Was ergibt das? 10
2. Was ist der nächste Summand $k + 1$ ? 5
3. Addiere ihn: Was ist die neue Summe $1 + 2 + 3 + 4 + 5$ ? 15
4. Was liefert die Formel für $k + 1 = 5$ , also $\dfrac{5 \cdot 6}{2}$ ? 15
11.
Vollziehe den Induktionsschritt für $1 + 3 + \dots + (2n-1) = n^2$ mit Zahlen nach, mit $k = 6$ .
Lösung: 49
1. Laut Voraussetzung ist die Summe der ersten $6$ ungeraden Zahlen $6^2$ . Was ergibt das? 36
2. Was ist die nächste ungerade Zahl $2k + 1$ ? 13
3. Addiere sie: Was ist die neue Summe? 49
4. Was ist $(k+1)^2 = 7^2$ ? 49
12.
Welcher Satz ist die richtige Induktionsvoraussetzung beim Beweis von $2^n > n$ für alle $n \ge 1$ ?
1. a)Angenommen, $2^n > n$ für alle $n \ge 1$
2. b)Angenommen, $2^k > k$ für eine ganze Zahl $k \ge 1$
3. c)Angenommen, $2^{k+1} > k + 1$
4. d)Beweise, dass $2^1 > 1$
Lösung: Angenommen, $2^k > k$ für eine ganze Zahl $k \ge 1$
Die Induktionsvoraussetzung nimmt die Aussage für ein beliebiges $k$ an. Sie für alle $n$ oder für $k + 1$ anzunehmen heißt, das Ziel vorauszusetzen, und $2^1 > 1$ ist der Induktionsanfang.
13.
Der Induktionsschritt für " $n^3 - n$ ist durch $3$ teilbar" benutzt $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k$ . Prüfe das mit $k = 4$ .
Lösung: 60
1. Was ist $k^3 - k$ für $k = 4$ ? 60
2. Was ist $(k+1)^3 - (k+1)$ für $k = 4$ ? 120
3. Was ist die Differenz $120 - 60$ ? 60
4. Was ist $3k^2 + 3k$ für $k = 4$ ? 60
14.
Mit Induktion kann man auch beweisen, dass $n^3 - n$ durch $6$ teilbar ist. Berechne für $n = 6$ den Wert $\dfrac{6^3 - 6}{6}$ .
Lösung: 35
$6^3 - 6 = 216 - 6 = 210$ und $210 \div 6 = 35$ , eine ganze Zahl, wie die Aussage vorhersagt.
15.
Ein Schüler "beweist", dass $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ für alle $n \ge 1$ gilt. Die Algebra im Induktionsschritt ist korrekt. Was ist falsch?
1. a)Die Voraussetzung muss $P(k+1)$ sein, nicht $P(k)$
2. b)Nichts, die Aussage ist wahr
3. c)Der Induktionsanfang scheitert: Für $n = 1$ ist die linke Seite $1$ , die rechte $2$
4. d)Induktion kann man für Summen nicht benutzen
Lösung: Der Induktionsanfang scheitert: Für $n = 1$ ist die linke Seite $1$ , die rechte $2$
Für $n = 1$ : Die linke Seite ist $1$ , die rechte $\dfrac{1 \cdot 2}{2} + 1 = 2$ . Der Induktionsanfang scheitert, also startet die Kette nie. Tatsächlich ist die Behauptung für jedes $n$ falsch, denn die wahre Summe ist $\dfrac{n(n+1)}{2}$ .
16.
Vollziehe den Induktionsschritt für $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ mit Zahlen nach, mit $k = 5$ .
Lösung: 127
1. Laut Voraussetzung ist $1 + 2 + \dots + 2^5 = 2^6 - 1$ . Was ergibt das? 63
2. Was ist der nächste Summand $2^{k+1} = 2^6$ ? 64
3. Addiere ihn: Was ist die neue Summe? 127
4. Was ist $2^{k+2} - 1 = 2^7 - 1$ ? 127
17.
Der Induktionsschritt für $2^n > n$ benutzt die Kette $2^{k+1} = 2 \cdot 2^k > 2k \ge k + 1$ . Vollziehe sie mit $k = 5$ nach.
Lösung: 6
1. Was ist $2^k = 2^5$ ? 32
2. Was ist $2^{k+1} = 2 \cdot 2^5$ ? 64
3. Was ist $2k$ ? 10
4. Was ist $k + 1$ ? 6
18.
Die Formel $1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$ wird mit Induktion bewiesen. Rechne ihren Induktionsanfang und einen Induktionsschritt mit Zahlen durch.
Lösung: 40
1. Induktionsanfang: Was ist die rechte Seite für $n = 1$ , also $\dfrac{1 \cdot 2 \cdot 3}{3}$ ? (Die linke Seite ist $1 \cdot 2 = 2$ .) 2
2. Voraussetzung für $k = 3$ : Was ist $\dfrac{3 \cdot 4 \cdot 5}{3}$ ? 20
3. Was ist der nächste Summand $(k+1)(k+2)$ für $k = 3$ ? 20
4. Addiere ihn zum Wert der Voraussetzung. Was ist die neue Summe? (Vergleiche mit $\dfrac{4 \cdot 5 \cdot 6}{3}$ .) 40