Erste Aufgabe:
Zu zeigen:
für alle n ∈ N, n≥ 0 gilt:
$$\sum _{ k=0 }^{ n }{ \frac { k }{ { 2 }^{ k } } } =2-\frac { n+2 }{ { 2 }^{ n } }$$
Induktionsanker:
Für n=0 gilt:
$$\sum _{ k=0 }^{ 0 }{ \frac { k }{ { 2 }^{ k } } } =\frac { 0 }{ { 2 }^{ 0 } } =0=2-\frac { 0+2 }{ { 2 }^{ 0 } } =2-\frac { 2 }{ 1 } =0$$
Induktionsvoraussetzung:
Für festes m ≥ 0 gelte:
$$\sum _{ k=0 }^{ m }{ \frac { k }{ { 2 }^{ k } } } =2-\frac { m+2 }{ { 2 }^{ m } } $$
Induktionsbehauptung:
Dann gilt für m+1:
$$\sum _{ k=0 }^{ m+1 }{ \frac { k }{ { 2 }^{ k } } } =2-\frac { m+3 }{ { 2 }^{ m+1 } }$$
Beweis:
$$\sum _{ k=0 }^{ m+1 }{ \frac { k }{ { 2 }^{ k } } } =\left( \sum _{ k=0 }^{ m }{ \frac { k }{ { 2 }^{ k } } } \right) +\frac { m+1 }{ { 2 }^{ m+1 } } $$
wegen Induktionsvoraussetzung:
$$=2-\frac { m+2 }{ { 2 }^{ m } } +\frac { m+1 }{ { 2 }^{ m+1 } } $$
$$=2-\frac { 2m+4 }{ { 2 }^{ m+1 } } +\frac { m+1 }{ { 2 }^{ m+1 } } $$
$$=2+\frac { -2m-4+m+1 }{ { 2 }^{ m+1 } } $$
$$=2+\frac { -m-3 }{ { 2 }^{ m+1 } } $$
$$=2-\frac { m+3 }{ { 2 }^{ m+1 } } $$
q.e.d.
Damit gilt wegen des Axioms von der vollständigen Induktion \(\sum _{ k=0 }^{ n }{ \frac { k }{ { 2 }^{ k } } }=2-\frac { n+2 }{ { 2 }^{ n } }\) für alle n ∈ N , n ≥ 0
Zweite Aufgabe:
Zu zeigen:
Für alle n ∈ N, n ≥ 1 gilt:
$$\sum _{ k=1 }^{ n }{ \frac { 1 }{ k } } <2n$$
Induktionsanker:
Für n=1 gilt:
$$\sum _{ k=1 }^{ 1 }{ \frac { 1 }{ k } } =\frac { 1 }{ 1 } =1<2=2*1$$
Induktionsvoraussetzung:
Für festes m ≥ 1 gelte:
$$\sum _{ k=1 }^{ m }{ \frac { 1 }{ k } } <2m$$
Induktionsbehauptung:
Dann gilt für m+1:
$$\sum _{ k=1 }^{ m+1 }{ \frac { 1 }{ k } } <2(m+1)=2m+2$$
Beweis:
$$\sum _{ k=1 }^{ m+1 }{ \frac { 1 }{ k } } =\left( \sum _{ k=1 }^{ m }{ \frac { 1 }{ k } } \right) +\frac { 1 }{ m+1 } $$
wegen Induktionsvoraussetzung
$$<2m+\frac { 1 }{ m+1 }$$
Für m ≥ 1 gilt: \(\frac { 1 }{ m+1 } <1<2\) , also:
$$ <2m+2=2(m+1)$$
q.e.d.
Damit gilt wegen des Axioms von der vollständigen Induktion \(\sum _{ k=1 }^{ n }{ \frac { 1 }{ k } }<2n\) für alle n ∈ N , n ≥ 1
