Vollständige Induktion - Institut für Mathematik

Fachschaft Mathematik
Institut für Mathematik
Humboldt-Universität zu Berlin
Warm-Up
WS 2015/16
Übungsaufgaben
Vollständige Induktion
Aufgabe 1 Man beweise folgende Formel:
n
X
3
i =
i=1
n(n + 1)
2
2
.
Lösung:
2 2
2
n = 1 : 13 =
Induktionsanfang
Induktionsvoraussetzung
⇐⇒ 1 = 1
n
X
n(n + 1) 2
3
i =
2
X
i=1
Induktionsbehauptung
n+1
X
3
i =
i=1
(n + 1)(n + 2)
2
2
Beweis.
n+1
X
3
i =
i=1
n(n + 1)
2
2
+ (n + 1)3
(nach Voraussetzung)
n2 (n + 1)2 + 4(n + 1)3
(n2 + 4(n + 1))(n + 1)2
=
4
4
2
2
2
(n + 4n + 4)(n + 1)
(n + 2) (n + 1)2
(n + 2)(n + 1) 2
=
=
=
4
4
2
=
Aufgabe 2 Man beweise folgende Formel für x 6= 1:
n
X
i=0
Lösung:
Induktionsanfang
n = 0 : x0 =
x1 −1
x−1
=1
X
–1–
xi =
xn+1 − 1
.
x−1
Fachschaft Mathematik
Institut für Mathematik
Humboldt-Universität zu Berlin
Warm-Up
WS 2015/16
n
X
Induktionsvoraussetzung
xi =
i=0
n+1
X
Induktionsbehauptung
xn+1 − 1
x−1
xi =
xn+2 − 1
x−1
xi =
xn+1 − 1
+ xn+1
x−1
i=0
Beweis.
n+1
X
i=0
=
(nach Voraussetzung)
xn+2 − 1
xn+1 − 1 + xn+2 − xn+1
=
x−1
x−1
n
X
Aufgabe 3 Man beweise folgende Formel:
i(i + 1) =
i=1
n(n + 1)(n + 2)
.
3
Lösung:
Induktionsanfang
n=1: 1·2=
Induktionsvoraussetzung
n
X
1·2·3
3
i(i + 1) =
i=1
n+1
X
Induktionsbehauptung
i=1
=2
i(i + 1) =
X
n(n + 1)(n + 2)
3
(n + 1)(n + 2)(n + 3)
3
Beweis.
n+1
X
i(i + 1) =
i=1
=
n(n + 1)(n + 2)
+ (n + 1)(n + 2)
3
(nach Voraussetzung)
n(n + 1)(n + 2) + 3(n + 1)(n + 2)
(n + 1)(n + 2)(n + 3)
=
3
3
–2–
Fachschaft Mathematik
Institut für Mathematik
Humboldt-Universität zu Berlin
Warm-Up
WS 2015/16
n
Q
Aufgabe 4 Man beweise folgende Formel:
(1 −
i=2
1
)
i2
=
n+1
2n
für alle n ≥ 2.
Lösung:
Induktionsanfang
n = 2 : (1 − 14 ) =
3
4
n
Q
=
Induktionsvoraussetzung
(1 −
i=2
n+1
Q
(1 −
Induktionsbehauptung
i=2
1
)
i2
1
)
i2
=
=
2+1
2·2
X
n+1
2n
n+2
2n+2
Beweis.
n+1
Y
n
(1 −
i=2
Y
1
1
1
) = (1 −
) · (1 − 2 )
2
2
i
(n + 1)
i
i=2
1
n+1
= (1 −
)·
(n + 1)2
2n
n(n + 2) n + 1
·
=
(n + 1)2
2n
n+2
=
2n + 2
(nach Voraussetzung)
Aufgabe 5 Man beweise folgende Formel: n! > 2n für alle n ≥ 4.
Lösung:
Induktionsanfang
n = 4 : 4! = 24 > 16 = 24
Induktionsvoraussetzung
Induktionsbehauptung
X
n! > 2n
(n + 1)! > 2n+1
Beweis.
(n + 1)! = (n + 1) · n! > (n + 1) · 2n > 2 · 2n = 2n+1
–3–
Fachschaft Mathematik
Institut für Mathematik
Humboldt-Universität zu Berlin
Warm-Up
WS 2015/16
Aufgabe 6 Man beweise, dass man jeden glatten Betrag größer 7 so mit Geldscheinen im
Wert von 3 und 5 bezahlen kann, dass man kein Wechselgeld erhält.
Lösung: Formale Schreibweise der Aufgabe:
∀x ∈ N mit x > 7 ∃m, n ∈ N0 :
x = 3m + 5n.
Induktionsanfang
x = 8 : 8 = 1 · 3 + 1 · 5;
x = 9 : 9 = 3 · 3 + 0 · 5;
Induktionsvoraussetzung
Induktionsbehauptung
x = 10 : 10 = 0 · 3 + 2 · 5 X
Für ein x > 7 gibt es m, n ∈ N0 : mit x = 3m + 5n
Dann gilt für x + 3 dass m0 , n0 ∈ N0 : mit x = 3m0 + 5n0
Beweis. Sei x = 3m + 5n. Dann gilt für
IV
x + 3 = (3m + 5n) + 3 = 3(m + 1) + 5n
In diesem Beweis haben wir also zuerst gezeigt, dass die Behauptung für die ersten drei
Zahlen 8, 9, 10 gilt, und dann gesehen, dass sie falls sie für eine Zahl gilt, auch für die um
drei größere Zahl gilt. Somit ist der Beweis erbracht.
Zusatzaufgabe 1 Man beweise folgende Formel:
n
X
n(2n − 1)(2n + 1)
(2i − 1)2 =
.
3
i=1
Lösung:
Induktionsanfang
n = 1 : 12 =
Induktionsvoraussetzung
n
X
3
3
⇐⇒ 1 = 1
(2i − 1)2 =
i=1
Induktionsbehauptung
n+1
X
(2i − 1)2 =
i=1
X
n(2n − 1)(2n + 1)
3
(n + 1)(2n + 1)(2n + 3)
3
–4–
Fachschaft Mathematik
Institut für Mathematik
Humboldt-Universität zu Berlin
Warm-Up
WS 2015/16
Beweis.
n+1
X
n
X
(2i − 1) =
(2i − 1)2 + (2(i + 1) − 1)2
2
i=1
i=1
n(2n − 1)(2n + 1)
+ (2n + 1)2
(nach Voraussetzung)
3
n(2n − 1) + 3(2n + 1) (2n + 1)
n(2n − 1)(2n + 1) + 3(2n + 1)2
=
=
3
3
(2n2 + 5n + 3)(2n + 1)
(n + 1)(2n + 3)(2n + 1)
=
=
3
3
=
Zusatzaufgabe 2 Man beweise folgende Formel:
n
X
i=1
i(i+1)(i+2) =
n(n + 1)(n + 2)(n + 3)
.
4
Lösung:
Induktionsanfang
n=1: 1·2·3=
Induktionsvoraussetzung
n
X
1·2·3·4
4
=6
i(i + 1)(i + 2) =
i=1
Induktionsbehauptung
n+1
X
i(i + 1)(i + 2) =
i=1
X
n(n + 1)(n + 2)(n + 3)
4
(n + 1)(n + 2)(n + 3)(n + 4)
4
Beweis.
n+1
X
i(i + 1)(i + 2) =
i=1
n(n + 1)(n + 2)(n + 3)
+ (n + 1)(n + 2)(n + 3)
4
(nach Voraussetzung)
n(n + 1)(n + 2)(n + 3) + 4(n + 1)(n + 2)(n + 3)
4
(n + 1)(n + 2)(n + 3)(n + 4)
=
4
=
–5–
Fachschaft Mathematik
Institut für Mathematik
Humboldt-Universität zu Berlin
Warm-Up
WS 2015/16
Zusatzaufgabe 3 Man beweise folgende Formel: n ·
√
n>n+
√
n für alle n ≥ 4.
Lösung:
√
√
4=8>6=4+ 4 X
√
√
Induktionsvoraussetzung n · n > n + n
√
√
Induktionsbehauptung (n + 1) n + 1 > n + 1 + n + 1
Induktionsanfang
n=4:4·
Beweis.
√
√
√
√
√
(n + 1) n + 1 = n n + 1 + n + 1 > n n + n + 1
√
√
√
>n+ n+ n+1>n+1+ n+1
–6–

Download Report