Vollständige Induktion Ungleichung

12.04.2020, 13:54

RonaldosKuzeng

Vollständige Induktion Ungleichung

Meine Frage:
Aufgabe:
$\begin{eqnarray*} \frac{n}{2}<1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{2^{n}-1}<n, \quad \end{eqnarray*}$ und für $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$

Meine Ideen:
Problem/Ansatz:

Den Induktionsanfang habe ich schon hinter mir. Beim Induktionsschritt $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$ habe ich mir folgende Gedanken gemacht:
1. $\begin{eqnarray*} \frac{n+1}{2}<1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{2^{n}-1}+\frac{1}{2^{n}}+\frac{1}{2^{n}+1}+\frac{1}{2^{n}+2}+\cdots+\frac{1}{2^{n+1}-1}<n+1 \end{eqnarray*}$

2. $\begin{eqnarray*} \frac{n}{2}+\frac{1}{2}<1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{2^{n}-1}+\frac{1}{2^{n}}+\frac{1}{2^{n}+1}+\frac{1}{2^{n}+2}+\cdots+\frac{1}{2^{n+1}-1}<n+1 \end{eqnarray*}$

Jetzt möchte ich die Induktionsannahme einsetzen und aus der Ungleichung rausnehmen:
3. $\begin{eqnarray*} \frac{1}{2}<\frac{1}{2^{n}}+\frac{1}{2^{n}+1}+\frac{1}{2^{n}+2}+\cdots+\frac{1}{2^{n+1}-1}<1 \end{eqnarray*}$

Falls das überhaupt Sinn ergibt, was ich bisher gemacht habe, würde ich euch gerne um Rat bitten, wie ich dann die 3. Zeile beweise.

12.04.2020, 14:00

Elvis

Auf diesen Beitrag antworten »

Das kann man nicht beweisen, weil $\begin{eqnarray*} \frac 1 2+\frac 1 3+ \frac 14 >1 \end{eqnarray*}$ schon für $\begin{eqnarray*} n=1 \end{eqnarray*}$ ist.

12.04.2020, 14:26

RonaldosKuzeng

Auf diesen Beitrag antworten »

@Elvis
@Elvis deshalb steht auch direkt oben in der Aufgabenstellung für $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$

12.04.2020, 14:37

Elvis

Auf diesen Beitrag antworten »

Das ist egal, dann addiere ein paar mehr Terme, das wird immer größer als 1. Die harmonische Reihe divergiert bestimmt gegen unendlich.
Die Abschätzung nach oben dürfte im Induktionsschritt auch nicht das Problem sein, nach unten ist kniffliger.

12.04.2020, 15:19

RonaldosKuzeng

Auf diesen Beitrag antworten »

@Elvis
@Elvis heißt das also, dass man das gar nicht beweisen kann bzw. dass es Gegenbeispiele gibt?

12.04.2020, 16:22

Elvis

Auf diesen Beitrag antworten »

Nein, das heißt es nicht. Ich kann es nur nicht beweisen.
Die Summe S, die bei dir unter 3. steht ist kleiner als (2^n-1)/(2^n)<1. Die Abschätzung 1/2<S fehlt mir noch.

12.04.2020, 16:26

Luftikus

Auf diesen Beitrag antworten »

RE: Vollständige Induktion Ungleichung ;(

Zitat:

Original von RonaldosKuzeng
öchte ich die Induktionsannahme einsetzen und aus der Ungleichung rausnehmen:
3. $\begin{eqnarray*} \frac{1}{2}<\frac{1}{2^{n}}+\frac{1}{2^{n}+1}+\frac{1}{2^{n}+2}+\cdots+\frac{1}{2^{n+1}-1}<1 \end{eqnarray*}$

Falls das überhaupt Sinn ergibt, was ich bisher gemacht habe, würde ich euch gerne um Rat bitten, wie ich dann die 3. Zeile beweise.

Ja, der Weg ist schon richtig:

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

und

$\begin{eqnarray*} \frac{1}{2} < \frac{2^n}{2^{n+1}-1} {, da} \quad 2^{n+1}-1 < 2^{n+1} \end{eqnarray*}$

13.04.2020, 00:41

Ulrich Ruhnau

Auf diesen Beitrag antworten »

RE: Vollständige Induktion Ungleichung ;(

Zitat:

Original von RonaldosKuzeng
Meine Frage:
Aufgabe:
$\begin{eqnarray*} \frac{n}{2}<1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{2^{n}-1}<n, \quad \end{eqnarray*}$ und für $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$

Sei $\begin{eqnarray*} n=2 \end{eqnarray*}$ $\begin{eqnarray*} \qquad\frac{2}{2}<1+\underbrace{\frac{1}{2}+\frac{1}{3}}_{< 1}<2 \end{eqnarray*}$
Sei $\begin{eqnarray*} n=3 \end{eqnarray*}$ $\begin{eqnarray*} \qquad\frac{3}{2}<1+\underbrace{\frac{1}{2}+\frac{1}{3}}_{< 1}+\underbrace{\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}}_{< 1}<3 \end{eqnarray*}$

Hier habe ich die Idee aufgezeigt, wie man die endliche Reihe nach oben abschätzt. So ähnlich geht das auch nach unten.

13.04.2020, 07:33

Elvis

Auf diesen Beitrag antworten »

Prima, jetzt sind hier schon vier Leute, die es nicht können. Big Laugh

13.04.2020, 08:50

Leopold

Auf diesen Beitrag antworten »

Setze $\begin{align*} m = 2^n \end{align*}$ . In der Rechnung

$\begin{align*} \sum_{k=0}^{m-1} \frac{1}{m+k} \ = \ \underbrace{\sum_{k=0}^{m-1} \frac{1}{1 + \frac{k}{m}} \cdot \frac{1}{m}}_{\text{(1)}} \ = \ \frac{1}{m} - \frac{1}{2m} + \ \underbrace{\sum_{k=1}^m \frac{1}{1 + \frac{k}{m}} \cdot \frac{1}{m}}_{\text{(2)}} \end{align*}$

erkennt man $\begin{align*} \text{(1)} \end{align*}$ als Ober- und $\begin{align*} \text{(2)} \end{align*}$ als Untersumme des Integrals $\begin{align*} \int_1^2 \frac{\dd x}{x} \ = \ \ln(2) \end{align*}$ , womit

$\begin{align*} \ln(2) \ < \ \sum_{k=0}^{m-1} \frac{1}{m+k} \ < \ \frac{1}{2m} + \ln(2) \end{align*}$

oder auch

$\begin{align*} \ln(2) \ < \ \sum_{k=0}^{2^n-1} \frac{1}{2^n+k} \ < \ \frac{1}{2^{n+1}} + \ln(2) \end{align*}$

folgt. Was da im Induktionsschritt dazukommt, unterscheidet sich also immer weniger von $\begin{align*} \ln(2) \end{align*}$ .

13.04.2020, 09:58

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Meine Abschätzung nach oben und nach unten, diesmal in Summenschreibweise für $\begin{eqnarray*} n\ge 2 \end{eqnarray*}$ :

$\begin{eqnarray*} \sum\limits_{j=1}^{2^n-1} \frac 1j=\sum\limits_{k=1}^{n} \sum\limits_{j=2^{k-1}}^{2^k-1} \frac 1j\quad <\quad\sum\limits_{k=1}^{n} \underbrace{\sum\limits_{j=2^{k-1}}^{2^k-1} \frac 1{2^{k-1}}}_{2^{k-1}\,\text{Summanden}} =\sum\limits_{k=1}^{n} 1=n \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{j=1}^{2^n-1} \frac 1j=\sum\limits_{k=1}^{n} \sum\limits_{j=2^{k-1}}^{2^k-1} \frac 1j\quad >\quad\sum\limits_{k=1}^{n} \underbrace{\sum\limits_{j=2^{k-1}}^{2^k-1} \frac 1{2^k}}_{2^{k-1}\,\text{Summanden}} =\sum\limits_{k=1}^{n} \frac 12=\frac n2 \end{eqnarray*}$

Das sollte meiner Meinung nach als Beweis genügen, sodaß wir hier die vollständige Induktion nicht brauchen.

13.04.2020, 11:02

Luftikus

Auf diesen Beitrag antworten »

Beweis mit vollständiger Induktion steht doch schon da.
Oder was ist an meinem Beweis des Induktionsschritts unverständlich?

Neue Frage »

Antworten »

Vollständige Induktion Ungleichung

Verwandte Themen