\(\displaystyle\sum_{k=1}^{2^n} \frac{1}{k} \geq 1 + \frac{n}{2}\)
Beweisen Sie die obige Aussage mittels vollständiger Induktion.
IA: \(\displaystyle\sum_{k=1}^{2^1} \frac{1}{k} = \frac{1}{1} + \frac{1}{2} = 1,5 \geq \frac{1}{2} = 1 + \frac{n}{2}\)
IS: \(\displaystyle\sum_{k=1}^{2^{n+1}} \frac{1}{k} = \frac{1}{n+1} + \displaystyle\sum_{k=1}^{2^{n}} \frac{1}{k} \geq 1 + \frac{n}{2} + \frac{1}{2} = 1 + \frac{n + 1}{2}\)
Wie komme ich hier weiter?
Ich bin mir nicht sicher bei den Formalitäten, aber ich kann mit ziemlicher Sicherheit sagen, dass bei deinem IS nicht einfach \(\frac{1}{1+n}\) hinzu kommt sondern wieder das Summenzeichen nur mit einem k-Startwert von \(2^n+1\) anstatt 1. Weiß nicht ob dir das weiterhilft. Krieg hier im Forum die Zeichen irgendwie nicht so hin.
+26367 Vollständige Induktion \(\sum \limits_{k=1}^{2^n} \dfrac{1}{k} \geq 1 + \dfrac{n}{2}\)
Induktionsanfang:
\(\begin{array}{|lrcll|} \hline n=1: & \sum \limits_{k=1}^{2^1} \dfrac{1}{k} = \dfrac{1}{1} + \dfrac{1}{2} = \dfrac{3}{2} \geq \dfrac{3}{2} = \dfrac{1}{1} + \dfrac{1}{2} \ \checkmark \\ \hline \end{array}\)
Induktionsannahme: \(\sum \limits_{k=1}^{2^n} \dfrac{1}{k} \geq 1 + \dfrac{n}{2}\)
Induktionsschritt:
\(\sum \limits_{k=1}^{2^{n+1}} \dfrac{1}{k} \geq 1 + \dfrac{n+1}{2} \\ \)
\(\begin{array}{|rcll|} \hline \mathbf{\sum \limits_{k=1}^{2^{n+1}} \dfrac{1}{k} } &\geq& \mathbf{ 1 + \dfrac{n+1}{2} =1 + \dfrac{n}{2} +\dfrac{1}{2} } \\\\ \hline \\ \sum \limits_{k=1}^{2^{n+1}} \dfrac{1}{k} &=& \sum \limits_{k=1}^{2^{n}} \dfrac{1}{k} + \sum \limits_{k=2^{n}+1}^{2^{n+1}} \dfrac{1}{k} \\ &\geq& 1 + \dfrac{n}{2} + \sum \limits_{k=2^{n}+1}^{2^{n+1}} \underbrace{\dfrac{1}{k}}_{\geq \dfrac{1}{2^{n+1}} ^{1)} } \quad \text{nach Induktionsannahme} \\ &\geq& 1 + \dfrac{n}{2} + \sum \limits_{k=2^{n}+1}^{2^{n+1}} \dfrac{1}{2^{n+1} } \quad 2^n \text{Summanden} ^{2)} \\ &=& 1 + \dfrac{n}{2} + 2^n\left( \dfrac{1}{2^{n+1} } \right) \\ &=& 1 + \dfrac{n}{2} + 2^{n-n-1} \\ &=& 1 + \dfrac{n}{2} +\dfrac{1}{2} \ \checkmark\\ \hline \end{array} \)
\(\begin{array}{|lrcll|} \hline ^{1)} \text{Beispiel n=2: } & \sum \limits_{k=2^{2}+1}^{2^{2+1}} \dfrac{1}{k} = \sum \limits_{k=5}^{8} \dfrac{1}{k} = \dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{7}+\dfrac{1}{8} \geq 4\cdot \dfrac{1}{8} \\ \hline \end{array} \)
\(\begin{array}{|lrcll|} \hline ^{2)} & (2^n+1)-2^n &\ldots& 2^{n+1} - (2^n) \\ & 1 &\ldots& 2\cdot 2^{n} - (2^n) \\ & 1 &\ldots& 2^n \\ \hline \end{array}\)
