Vollständige Induktion bei dieser Ungleichung mit einer Summe

Question

Aufgabe:

Zeigen Sie die Richtigkeit der folgenden Aussage durch vollständige Induktion:

$\sum \limits_{k=1}^{2^{n}} \frac{1}{k} \geq 1+\frac{n}{2}$

Answer 1

Aloha :)

Willkommen in der Mathelounge... \o/

Der Induktionsanfang bei $n=0$ ist klar:$$\sum\limits_{k=1}^{2^n}\frac1k=\sum\limits_{k=1}^{2^0}\frac1k=\sum\limits_{k=1}^{1}\frac1k=1\ge1+\frac02=1+\frac n2\quad\checkmark$$

Im Induktionsschritt $n\to n+1$ können wir nun die Gültigkeit der Gleichung bis zu $n$ voraussetzen. Dazu spalten wir die Summe in 2 Teilsummen auf.$$\sum\limits_{k=1}^{2^{n+1}}\frac1k=\sum\limits_{k=1}^{2^n}\frac1k+\sum\limits_{k=2^n+1}^{2^{n+1}}\frac1k$$Die erste Summe können wir durch die Induktionsvoraussetzung abschätzen. Bei der zweiten Summe nutzen wir aus, dass ein Bruch kleiner wird, wenn wir seinen Nenner vergrößern. Dazu setzen wir für alle Summanden das maximale $k$ ein, also $k=2^{n+1}$:$$\sum\limits_{k=2^n+1}^{2^{n+1}}\frac1k\ge\sum\limits_{k=2^n+1}^{2^{n+1}}\frac1{2^{n+1}}=\frac1{2^{n+1}}\sum\limits_{k=2^n+1}^{2^{n+1}}\!\!1=\frac1{2^{n+1}}\cdot\left(2^{n+1}-2^n\right)=\frac1{2^{n+1}}\cdot2^n\cdot\left(2-1\right)=\frac12$$

Insgesamt lautet also unsere Abschätzung:$$\sum\limits_{k=1}^{2^{n+1}}\frac1k=\sum\limits_{k=1}^{2^n}\frac1k+\sum\limits_{k=2^n+1}^{2^{n+1}}\frac1k\ge\left(1+\frac n2\right)+\frac12=1+\frac{n+1}2\quad\checkmark$$