\documentclass[11pt]{article}

\newcounter{blatt}
\newcounter{aufgabe}
\setcounter{blatt}{2}
\setcounter{aufgabe}{1}

\include{AnaHdrMusterLoes}

\begin{document}

\begin{center}
{\LARGE Musterlösung zu Blatt \theblatt, Aufgabe \theaufgabe}
\end{center}

\section{Aufgabenstellung}
Die $n-te$ harmonische Summe $H_n$ ist für eine natürliche Zahl $n \geq 1 $ definiert durch:
\begin{center}
$H_n:=\displaystyle \sum^{n}_{k=1}{\frac{1}{k}}$
\end{center}
\flushleft
a) Zeigen Sie: Für alle natürlichen Zahlen $m \geq 1$ gilt:
\begin{center}
$H_{2^m} \geq 1+\frac{m}{2}$.
\end{center}
\flushleft
b) Zeigen Sie, dass für alle natürlichen Zahlen $n \geq 1$ gilt:
\begin{center}
$ \displaystyle \sum^n_{k=1}H_k=(n+1)H_n-n $
\end{center} 


\section{Beweisidee}
\paragraph{"`Worum geht's?"':}
Offensichtlich sollen einmal eine Ungleichung und einmal eine Gleichung bewiesen werden. Beide beinhalten eine Partialsumme der unendlichen harmonischen Reihe, für die keine explizite Darstellung angegeben werden kann. 
\paragraph{"`Wie mach' ich das?"':}
a) Es bietet sich die vollständige Induktion an. Besonders wichtig beim Abschätzen der einzelnen Terme ist, dass man immer in die gleiche Richtung abschätzt. Dabei ist es nicht möglich eine Abschätzung in die eine Richtung mit einer in die andere Richtung aufzuheben. Bei der harmonischen Reihe kann man z.B. das kleinste Folgeglied verwenden und entsprechend mit der Anzahl der aufsummierten Folgeglieder multiplizieren. Das Ergebnis wäre ein kleinerer Wert, als der tatsächliche Wert der Reihe. \\
Während man auch bei Teilaufgabe b) mit der vollständigen Induktion (siehe Varianten) argumentieren kann, soll hier lediglich durch Umsortierung der Summanden die Aussage bewiesen werden. Dabei ist es wichtig darauf zu achten, dass keine Summanden verloren gehen. Ebenfalls ist es hilfreich zielgerichtet so umzuformen, dass man das gewünschte Ergebnis erhält, z.B. durch gleichzeitige Addition und Subtraktion einer Zahl bzw. Variablen. 


\section{Lösung}

a) Diese Abschätzung lässt sich mit vollständiger Induktion nach $m$ zeigen.\\ \bigskip
\underline{Induktionsanfang}
\flushleft
Für $m=1$ ist
\begin{center}
$H_{2^m}=H_{2}=\displaystyle \sum^2_{k=1}\frac{1}{k}=\frac{1}{1}+\frac{1}{2}=\frac{3}{2} \geq 1+\frac{1}{2}=1+\frac{m}{2}$
\end{center}
 
\underline{Induktionsvoraussetzung}
\flushleft

Für alle $j \leq m$, $j \in \mathbb{N}$ sei die folgende Aussage wahr

\begin{center}
$H_{2^j} \geq 1+\frac{j}{2}$
\end{center}

\underline{Induktionsschritt}
\flushleft
\begin{center}
$H_{2^{m+1}}=\displaystyle \sum^{2^{m+1}}_{k=1}=\displaystyle \sum^{2^{m}}_{k=1}+\displaystyle \sum^{2^{m+1}}_{k=2^m+1}$
\end{center}

Die Summe wird also aufgespalten. Die Motivation dafür ist die nun folgende Möglichkeit, die Induktionsvoraussetzung zu verwenden.

\begin{center}
$H_{2^{m+1}}=\displaystyle \sum^{2^{m}}_{k=1}+\displaystyle \sum^{2^{m+1}}_{k=2^m+1} \geq 1+\frac{m}{2}+ \displaystyle \sum^{2^{m+1}}_{k=2^m+1}$
\end{center}

Auch die zweite Summe lässt sich abschätzen. Sie beinhaltet genau $2^{m+1}-2^{m}=2\cdot2^{m}-2^{m}=2^{m}$ Summanden. Der kleinste Summand ist sicherlich $\frac{1}{2^{m+1}}$, da das der Kehrwert der größten natürlichen Zahl ist. Die Summe $\sum^{2^{m+1}}_{k=2^m+1}$ ist dann, da jeder Summand größer oder gleich $\frac{1}{2^{m+1}}$ ist, nach unten abschätzbar mit

\begin{center}
$\displaystyle \sum^{2^{m+1}}_{k=2^m+1} \geq {2^m}\frac{1}{2^{m+1}}=\frac{1}{2}$
\end{center}

Setzt man diese Ungleichung nun für $ \sum^{2^{m+1}}_{k=2^m+1}$, so bekommt man den gesuchten Induktionsschritt

\begin{center}
$H_{2^{m+1}}=\displaystyle \sum^{2^{m}}_{k=1}+\displaystyle \sum^{2^{m+1}}_{k=2^m+1} \geq 1+\frac{m}{2}+\displaystyle \sum^{2^{m+1}}_{k=2^m+1}\geq 1+\frac{m}{2}+\frac{1}{2}=1+ \frac{m+1}{2}$
$\Rightarrow H_{2^{m+1}} \geq 1+ \frac{m+1}{2}$
\end{center} 
(Möchte man diese Abschätzung nach unten durch eine auf $[1,\infty]$-stetige Funktion beschreiben, ist dies $f(x)=1+\frac{\log_2x}{2}=1+\frac{\ln x}{2 \ln 2}$.) 
\par \flushleft
b) Zunächst vertausche man die Summationsreihenfolge
\begin{center}
$ \displaystyle \sum^n_{k=1} H_k = \displaystyle \sum^n_{k=1} \sum^k_{j=1}\frac{1}{j}
=\underbrace{\displaystyle \sum^1_{j=1}\frac{1}{j}+ \dots + \displaystyle \sum^n_{j=1} \frac{1}{j}}_{n}$
\end{center}

In jeder Summen steckt ein Summand $\frac{1}{1}$, also $n-$mal. Der Summand $\frac{1}{2}$ taucht dementsprechend in jeder Summe, außer $\sum^1_{j=1}\frac{1}{j}$ auf, also $(n-1)-$mal. Setzt man dies sukszessive fort erhält man

\begin{center}
$ \displaystyle \sum^n_{k=1}H_k=\sum^n_{k=1}\sum^k_{j=1}\frac{1}{j}
=\underbrace{\sum^1_{j=1}\frac{1}{j} \dots \sum^n_{j=1} \frac{1}{j}}_{n}=\underbrace{n\frac{1}{1}+(n-1)\frac{1}{2}+\dots+1\cdot \frac{1}{n}}_{n}=\sum^n_{j=1}\frac{n-j+1}{j}$
\end{center} 

Man kann schließlich den Bruch in ein Summe zerlegen und erhält die gewünschte Aussage

\begin{center}
$\displaystyle \sum^n_{k=1}H_k=\dots=\sum^n_{j=1}\frac{n-j+1}{j}=\sum^n_{j=1}\left(\frac{n+1}{j}+\frac{j}{j}\right)=\sum^n_{j=1} \frac{n+1}{j}+\sum^n_{j=1} 1=(n+1)\sum^n_{j=1}\frac{1}{j}+n=(n+1)H_n+n$
\end{center}

\paragraph{Variante:} 
Alternativ lässt sich der Beweis von Teilaufgabe b) auch mit Induktion führen. \par \flushleft
\underline{Induktionsanfang}
\flushleft
Für $n=1$ gilt
\begin{center}
$\displaystyle \sum^n_{k=1}H_k=\sum^1_{k=1}H_k=\frac{1}{1}=1=(1+1)\frac{1}{1}-1=(n+1)H_n-n $
\end{center}

\underline{Induktionsvoraussetzung}
\flushleft

Für alle $j \leq n$, $j \in \mathbb{N}$ gelte
\begin{center}
$\displaystyle \sum^j_{k=1}H_k=(j+1)H_j-j$
\end{center}

\underline{Induktionsschritt}
\flushleft

\begin{center}


$\displaystyle \sum^{n+1}_{k=1}H_k=\sum^n_{k=1}H_k+\sum^{n+1}_{k=n+1}H_k=\sum^n_{k=1}H_k+H_{n+1}=(n+1)H_n-n+H_{n+1}=(n+1)H_n-n+H_{n+1}+\frac{n+1}{n+1}-\frac{n+1}{n+1}=(n+1)H_{n+1}+H_{n+1}-n-1=$\\$(n+2)H_{n+1}-(n+1)$
\end{center}
\bigskip
Damit hat man  $ \sum^n_{k=1}H_k=(n+1)H_n-n $ auch durch Induktion gezeigt.

\section{Variationen, Verallgemeinerungen, Abschwächungen}

Eine Verschärfung der Teilaufgabe a) ergibt sich zum Beispiel im Nachweis der folgenden Ungleichung

\begin{center}
$\ln(1+n)<H_n<1+\ln(1+n)$
\end{center}
Wie schon in der ursprünglichen Gleichung wird auch hier die harmonische Reihe durch eine Logarithmusfunktion angenährt. 
Verständlich wird diese Ungleichung, wenn wir die Treppenfunktion $f(x)=\frac{1}{[x]}$, deren Integral dann gerade die harmonische Reihe ist, betrachten. Entsprechend ist  $g(x)=\frac{1}{x} \leq f(x)$, aber $g(x) \neq f(x)$ und somit 
\begin{center}
$\displaystyle \int^{n+1}_1 \frac{1}{x} $ d$x < H_n $
\end{center}
Ebenso folgt für  $\displaystyle g'(x)=\left\{ \begin{array}{ccc} 1&$ für  $x<2 \\ \frac{1}{x-1}  &$ für $x\geq 2  \\ \end{array} \right. \Rightarrow g'(x) \geq f(x)$, aber $g'(x) \neq f(x)$ 
\begin{center}
$\displaystyle \Rightarrow 1+ \int^{n+1}_2 \frac{1}{x-1} $ d$x > H_n $\end{center}
Fasst man zusammen und rechnet man die Integrale aus, so ergibt sich 
\begin{center}
$\displaystyle \int^{n+1}_1 \frac{1}{x} $ d$x < H_n < 1+ \int^{n+1}_2 \frac{1}{x-1} $ d$x$ \\
$\ln (n+1)-\ln{1} < H_n < 1+\ln(n+1-1)-\ln(2-1) $\\
$\ln (n+1)  < H_n < 1+ \ln{n}< 1+\ln(n+1) $
\end{center}

Tatsächlich lässt sich die harmonische Reihe durch die Logarithmusfunktion für sehr große $n$ sehr gut approximieren. Dabei gilt
\begin{center}
$H_n\approx\ln{n}+\gamma$
\end{center}
Hierbei ist $\gamma$ eine Konstante, die Euler-Mascheroni-Konstante. Sie lässt sich verschiedentlich angeben, z.B.
\begin{center}
$\gamma=\displaystyle -\int^{\infty}_0 e^{-x}\ln{x} $ d$x \approx 0,57722$ \\
$\gamma=\displaystyle \lim_{s \rightarrow 1}\left(\zeta(s)-\frac{1}{s-1}\right)$ mit $\zeta(s)$ Riemannsche Zeta-Funktion.\\
\end{center}
Interessant für den hier betrachteten Fall ist jedoch ausschließlich, dass
\begin{center}
$\displaystyle \lim_{n \rightarrow \infty}\left(H_n-\ln{n}\right)=\gamma$
\end{center}

\section{Nutzen \& Anwendungen}
Die Aufgabe dient zur Erarbeitung des Verfahrens der vollständigen Induktion, ebenso wie der Übung im Umgang mit Ungleichungen und dem Summenzeichen. Sie zeigt aber auch, dass eine Induktion nicht immer notwendig ist und oft andere Wege zur Verfügung stehen, die formal einfacher und auch wesentlich kürzer sind. 
Eine Anwendung der harmonischen Reihe ist z.B. als Minorante. Sie kann also zum Beweis der Divergenz einer Reihe genutzt werden.

\begin{flushright}
{\footnotesize Pascal Reisert, \today}
\end{flushright}
\end{document}