Vollständige Induktion

26.10.2013, 21:08

Shalec

Vollständige Induktion

Moin,
ich habe mir mal Erstsemester-Aufgaben besorgt und wollt das mal wieder durchrechnen. Nun lautet die Aufgabe:

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

Über vollständige Induktion erhalte ich dann im Induktionsschritt:

$\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{IV}{\geq} 1+\frac{n}{2} +\sum\limits_{k=2^n+1}^{2^{n+1}} \frac{1}{k}<br /> = 1+\frac{n}{2} +\sum\limits_{k=1}^{2^{n}} \frac{1}{2^n+k} \end{eqnarray*}$

Der letzte Summand muss größer oder gleich 1/2 sein, damit die Behauptung war ist.

Kennt jemand einen Trick, wie man hier das zu Zeigende nachweisen kann? Mir fällt nichts mehr ein. Eine weitere Induktion ist zu aufwändig - daher muss der Trick rudimentär sein. Eine Partialbruchzerlegung lässt sich auch ausschließen, da dies eine Aufgabe aus dem 1. Semester in der 2. Woche ist.

Kann mir hier jemand helfen?

Viele Grüße und vielen Dank,
Shalec

//edit
Korrektur durchgeführt, Summationsgrenze wie vorgeschlagen angepasst smile

26.10.2013, 21:17

Che Netzer

Auf diesen Beitrag antworten »

Schätze die Summanden mit $\begin{eqnarray*} k\leq2^n \end{eqnarray*}$ ab. (in deinem ersten Umformungsschritt steckt übrigens ein Tippfehler bei der oberen Summationsgrenze)

26.10.2013, 22:42

jimmyt

Auf diesen Beitrag antworten »

RE: Vollständige Induktion Sum(k=1 to 2^n) 1/k >= n/2 + 1

Zitat:

Original von Shalec

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

Der letzte Summand muss größer oder gleich 1/2 sein, damit die Behauptung war ist.

Kennt jemand einen Trick, wie man hier das zu Zeigende nachweisen kann? Mir fällt nichts mehr ein. Eine weitere Induktion ist zu aufwändig - daher muss der Trick rudimentär sein.
...

Wie wäre es damit:

$\begin{eqnarray*} \sum\limits_{k=2^n+1}^{2^{n+1}} \frac{1}{k} = \underbrace{\frac{1}{2^n+1} + \frac{1}{2^n+2} + \dots + \frac{1}{2^{n+1}}}_{2^n\text{-mal}} \textcolor{red}{\geq} \underbrace{\frac{1}{2^{n+1}} + \frac{1}{2^{n+1}} + \dots + \frac{1}{2^{n+1}}}_{2^n\text{-mal}} = 2^n \cdot \frac{1}{2^{n+1}} = \frac{1}{2} \end{eqnarray*}$ Augenzwinkern

27.10.2013, 17:21

Shalec

Auf diesen Beitrag antworten »

RE: Vollständige Induktion Sum(k=1 to 2^n) 1/k >= n/2 + 1
Manchmal versperren einen die Bäume den Blick auf den Wald..
Danke!!

smile

edit von sulo: Vollzitat entfernt.

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen