Vollständige Induktion einer Ungleichung

07.05.2017, 19:01

keptain

Vollständige Induktion einer Ungleichung

Meine Frage:
Ich würde mich freuen wenn mir jemand kurz einen kleinen Denkanstoß geben könnte wie ich diese Ungleichung lösen soll bzw. wie man generell bei einer Induktion einer Summe mit einer Ungleichung vorgeht.

Vielen Dank im voraus.

$\begin{eqnarray*} \sum\limits_{k=1}^{2^{n}} \frac{1}{k} \geq 1+\frac{n}{2} \end{eqnarray*}$

Meine Ideen:
Induktionsanfang, Induktionsvoraussetzung und der Anfang des Induktionsbeweises fielen mir leicht. Ab hier hakt es:

$\begin{eqnarray*} \sum\limits_{k=1}^{2^{n+1}} \frac{1}{k} \geq 1+\frac{n}{2}+\frac{1}{2^{n+1}} \end{eqnarray*}$

Ich komme nachdem ich alles auf den selben Nenner bringe, noch auf:

$\begin{eqnarray*} =\frac{2^{n}\cdot n+1}{2^{n+1}} \end{eqnarray*}$

07.05.2017, 19:28

zinR

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung

Zitat:

Original von keptain
$\begin{eqnarray*} \sum\limits_{k=1}^{2^{n+1}} \frac{1}{k} \geq 1+\frac{n}{2}+\frac{1}{2^{n+1}} \end{eqnarray*}$

Diese Aussage kannst du stark verschärfen. Es ist ja $\begin{eqnarray*} \sum\limits_{k=1}^{2^{n+1}} \frac{1}{k} = \sum\limits_{k=1}^{2^{n}} \frac{1}{k} + \sum\limits_{k=2^n +1}^{2^{n+1}} \frac{1}{k} \end{eqnarray*}$ .

Wie viele Summanden hat die rechte Summe? Welcher ist der kleinste?

07.05.2017, 19:41

keptain

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
Da musst mir mal kurzen weiterhelfen, ich komme nicht darauf...

07.05.2017, 19:48

zinR

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
Wie viele Summanden hätte die Summe denn, wenn wir bei $\begin{eqnarray*} k=1 \end{eqnarray*}$ mit dem Summieren anfangen würden?

Davon schneiden wir von unten die ersten $\begin{eqnarray*} 2^n \end{eqnarray*}$ Summanden weg - diese stehen ja jetzt in der linken Summe. Wie viele bleiben?

07.05.2017, 20:19

keptain

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
Wir hätten von k=1 bis 2^n 2 Summanden und einen Dritten mit 2^(n+1) ?

07.05.2017, 20:31

zinR

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
So war das nicht gemeint.

Betrachte doch mal die Summe beispielhaft für ein paar $\begin{eqnarray*} n \in\mathbb{N} \end{eqnarray*}$ , vielleicht hilft das:

$\begin{eqnarray*} \sum\limits_{k=1}^2 \frac{1}{k} = 1 + \frac{1}{2} \end{eqnarray*}$ , d.h. zwei Summanden,

$\begin{eqnarray*} \sum\limits_{k=1}^{2^2} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} \end{eqnarray*}$ , d.h. $\begin{eqnarray*} 2^2 =4 \end{eqnarray*}$ Summanden.

Wie du sicherlich hier auch schon feststellen konntest, ist der kleinste Summand immer der letzte, im ersten Beispiel also $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ , im zweiten dann $\begin{eqnarray*} \frac{1}{4} \end{eqnarray*}$ .

Wenn wir jetzt wieder für ein beliebiges $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ von $\begin{eqnarray*} k=1 \end{eqnarray*}$ bis $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ summieren, wie viele Summanden haben wir? (D.h., wie viele Brüche addieren wir?)
Welcher ist der kleinste?

07.05.2017, 20:37

keptain

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
So war das gemeint. Wir haben 2^n+1 Summanden, mit 1/2^n+1 als kleinsten Summanden.

07.05.2017, 20:42

zinR

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
Die Anzahl der Summanden passt jetzt, wenn wir von $\begin{eqnarray*} k=1 \end{eqnarray*}$ aus summieren. Jetzt lassen wir aber die ersten $\begin{eqnarray*} 2^n \end{eqnarray*}$ Summanden weg. Wie viele bleiben?

Für $\begin{eqnarray*} k=2^{n+1} \end{eqnarray*}$ haben wir $\begin{eqnarray*} \frac {1}{2^{n+1}} \end{eqnarray*}$ , als kleinsten Summanden, ja.

Wenn du jetzt weißt, wie viele Summanden du hast, und welcher der kleinste ist, dann kannst du $\begin{eqnarray*} \sum\limits_{k=2^n +1}^{2^{n+1}} \frac{1}{k} \end{eqnarray*}$ prima nach unten abschätzen.

Du solltest auch, wenn du die LaTeX Umgebung nicht nutzt, immer Klammern setzen, um Missverständnisse zu vermeiden Augenzwinkern

07.05.2017, 20:48

keptain

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
Tut mir leid, was genau meinst du mit "nach unten abschätzen", deutsch ist nicht die sprache in der ich mich in der mathematik normalerweise ausdrücke..

07.05.2017, 21:03

zinR

Auf diesen Beitrag antworten »

RE: Vollständige Induktion einer Ungleichung
Naja, erinnere dich daran wo du hin willst:

$\begin{eqnarray*} \sum\limits_{k=1}^{2^{n+1}} \frac{1}{k} = \sum\limits_{k=1}^{2^n} \frac{1}{k} + \sum\limits_{k=2^n + 1}^{2^{n+1}} \frac{1}{k} \overset{!}\geq 1+ \frac{n+1}{2} \end{eqnarray*}$ , wobei das "!" andeuten soll, dass du das noch zeigen musst.

Auf die linke Summe lässt sich die Induktionsvoraussetzung anwenden, soweit stimmst du mir zu? (Das hast du ja am Anfang auch erfolgreich gemacht.)
Jetzt musst du noch etwas finden, das auf jeden Fall kleiner oder gleich dem rechten Teil der Summe ist. (Auf jeden Fall aber auch größer oder gleich $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ , sonst haut das mit der Induktion nicht mehr hin!)
Dafür haben wir gerade die Vorarbeit geleistet. Wir haben jetzt etwas, das auf jeden Fall kleiner oder gleich jedem einzelnen der anderen Summanden ist. In Formeln: $\begin{eqnarray*} \forall k \in \{2^n+1 , 2^n +2 , ... , 2^{n+1} \}: \frac{1}{k} \geq \frac{1}{2^{n+1}} \end{eqnarray*}$ .
Wir wissen auch, wie viele Summanden wir haben, also können wir damit die ganze rechte Summe $\begin{eqnarray*} \sum\limits_{k=2^n+1}^{2^{n+1}} \frac{1}{k} \end{eqnarray*}$ abschätzen, d.h. ein $\begin{eqnarray*} x \end{eqnarray*}$ finden, sodass $\begin{eqnarray*} \sum\limits_{k=2^n+1}^{2^{n+1}} \frac{1}{k} \geq x \end{eqnarray*}$ , wenn du so willst. Augenzwinkern

Neue Frage »

Antworten »

Vollständige Induktion einer Ungleichung

Verwandte Themen