Vollständige Induktion

Name:

Klasse:

Datum:

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
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$ ?
3.
Prüfe $1 + 3 + 5 + \dots + (2n-1) = n^2$ für $n = 6$ : Was ist $1 + 3 + 5 + 7 + 9 + 11$ ?
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
5.
Bevor du $2^n > n$ beweist, prüfe die ersten Dominosteine: Berechne $2^n$ für $n = 1, 2, 3$ .
6.
Prüfe die Formel $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ für $n = 3$ .
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?
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.
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$
10.
Vollziehe den Induktionsschritt für $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ mit Zahlen nach, mit $k = 4$ .
11.
Vollziehe den Induktionsschritt für $1 + 3 + \dots + (2n-1) = n^2$ mit Zahlen nach, mit $k = 6$ .
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$
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$ .
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}$ .
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
16.
Vollziehe den Induktionsschritt für $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ mit Zahlen nach, mit $k = 5$ .
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.
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.