Aufgabensammlung Mathematik: Abschätzung der harmonischen Reihe nach oben

Abschätzung der harmonischen Reihe nach oben

Beweise für alle natürlichen Zahlen $n\geq 1$ die folgende Ungleichung:

$\sum _{k=1}^{2^{n}-1}{1 \over k}\leq n$

Beweis

Aussageform, deren Allgemeingültigkeit für alle natürlichen Zahlen $n\geq 1$ bewiesen werden soll:

$\sum _{k=1}^{2^{n}-1}{1 \over k}\leq n$

1. Induktionsanfang:

$\sum _{k=1}^{2^{1}-1}{1 \over k}=\sum _{k=1}^{1}{1 \over k}=1\leq 1$

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

$\sum _{k=1}^{2^{n}-1}{1 \over k}\leq n$

2b. Induktionsbehauptung:

$\sum _{k=1}^{2^{n+1}-1}{1 \over k}\leq n+1$

2c. Beweis des Induktionsschritts:

Zunächst kann $\sum _{k=1}^{2^{n+1}-1}{1 \over k}$ in die zwei Summanden $\sum _{k=1}^{2^{n}-1}{1 \over k}$ und $\sum _{k=2^{n}}^{2^{n+1}-1}{1 \over k}$ aufgeteilt werden. Es ist $\sum _{k=1}^{2^{n}-1}{1 \over k}\leq n$ nach Induktionsvoraussetzung. In der zweiten Summe $\sum _{k=2^{n}}^{2^{n+1}-1}{1 \over k}$ durchläuft $k$ alle Werte zwischen $k=2^{n}$ und $k=2^{n+1}$. Damit ist in der zweiten Summe stets $k$ größer gleich $2^{n}$ und somit der Summand ${\frac {1}{k}}$ kleiner gleich ${\frac {1}{2^{n}}}=2^{-n}$. So lässt sich die Summe $\sum _{k=1}^{2^{n+1}-1}{1 \over k}$ nach oben abschätzen:

${\begin{aligned}\sum _{k=1}^{2^{n+1}-1}{1 \over k}&=\sum _{k=1}^{2^{n}-1}{1 \over k}+\sum _{k=2^{n}}^{2^{n+1}-1}{1 \over k}\\[5px]&\qquad \left\downarrow \ \sum _{k=1}^{2^{n}-1}{1 \over k}\leq n{\text{ nach Induktionsvoraussetzung}}\right.\\[5px]&\leq n+\sum _{k=2^{n}}^{2^{n+1}-1}\underbrace {1 \over k} _{\leq 2^{-n}}\\[5px]&\leq n+\sum _{k=2^{n}}^{2^{n+1}-1}2^{-n}\\[5px]&\qquad \left\downarrow \ \sum _{k=2^{n}}^{2^{n+1}-1}2^{-n}{\text{ hat }}2^{n}{\text{ Summanden}}\right.\\[5px]&=n+2^{n}\cdot 2^{-n}\\[5px]&=n+1\end{aligned}}$