Vollständige Induktion

29.03.2011, 19:05

GetTheFunkOut

Vollständige Induktion

Aufgabe:
Zeigen Sie durch vollständige Induktion: $\begin{eqnarray*} \sum\limits_{k=1}^{2^n} \frac{1}{k} \geq 1+\frac{n}{2} , n \in \mathbb N \vee n=0 \end{eqnarray*}$

Mein Lösungsansatz:
Induktionsanfang für n=0: $\begin{eqnarray*} \sum\limits_{k=1}^{2^0} \frac{1}{k}=1 \geq 1+ \frac{0}{2} \end{eqnarray*}$

Induktionsschritt von n auf n+1 unter der Induktionsvoraussetzung, dass $\begin{eqnarray*} \sum\limits_{k=1}^{2^n} \frac{1}{k} \geq 1+\frac{n}{2} \end{eqnarray*}$ für ein n bereits bewiesen wurde:

$\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} =\sum\limits_{k=1}^{2^n} \frac{1}{k} + \sum\limits_{k=1}^{2^n} \frac{1}{k+2^n} =\sum\limits_{k=1}^{2^n} \frac{1}{k} + \sum\limits_{k=1}^{2^n} \left( \frac{1}{k} \cdot \frac{1}{1 + \frac{2}{k}} \right) \geq 1 + \frac{n}{2} + (1 + \frac{n}{2}) \cdot \frac{1}{3} \end{eqnarray*}$

Ich hab jetzt einfach mal drauflosgerechnet und bin sehr unzufrieden - nicht nur, dass das Ergebnis für n=0 nicht gilt, sondern auch, weil mir das Ganze irgendwie nicht elegant vorkommt... Wahrscheinlich habe ich irgendwo einen elementaren Fehler gemacht smile

Irgendjemand eine Idee?

MfG, GetTheFunkOut

29.03.2011, 19:33

wogir

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von GetTheFunkOut
$\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} =\sum\limits_{k=1}^{2^n} \frac{1}{k} + \sum\limits_{k=1}^{2^n} \frac{1}{k+2^n} =\sum\limits_{k=1}^{2^n} \frac{1}{k} + \sum\limits_{k=1}^{2^n} \left( \frac{1}{k} \cdot \frac{1}{1 + \frac{2}{k}} \right) \geq 1 + \frac{n}{2} + (1 + \frac{n}{2}) \cdot \frac{1}{3} \end{eqnarray*}$

Ich hab jetzt einfach mal drauflosgerechnet und bin sehr unzufrieden - nicht nur, dass das Ergebnis für n=0 nicht gilt, sondern auch, weil mir das Ganze irgendwie nicht elegant vorkommt... Wahrscheinlich habe ich irgendwo einen elementaren Fehler gemacht smile

Irgendjemand eine Idee?

MfG, GetTheFunkOut

in der 4. Zeile müsste

$\begin{eqnarray*} ...=\sum\limits_{k=1}^{2^n} \frac{1}{k} + \sum\limits_{k=1}^{2^n} \left( \frac{1}{k} \cdot \frac{1}{1 + \frac{2^n}{k}} \right) \end{eqnarray*}$

stehen (beache das 2^n)

29.03.2011, 19:42

GetTheFunkOut

Auf diesen Beitrag antworten »

Danke für das Finden des Fehlers smile

, ich schau grad, ob das mein Problem vielleicht löst.
Prinzipiell muss ich aber jetzt schon zeigen, dass gilt: $\begin{eqnarray*} \sum\limits_{k=1}^{2^n} \frac{1}{1+ \frac{2^n}{k}} \geq \frac{1}{3} \end{eqnarray*}$ , oder?

MfG, GetTheFunkOut

29.03.2011, 19:49

wogir

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Hmmm... nö. Im Prinzip hast du wahrscheinlich richtig gedacht, du solltest

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

abschätzen gegen

$\begin{eqnarray*} \max_{k\in(1...2^n)}\left(\frac{1}{1 + \frac{2^n}{k}}\right)\sum\limits_{k=1}^{2^n} \frac{1}{k} \end{eqnarray*}$

und dann die Induktionsannahme benutzen.

29.03.2011, 19:59

GetTheFunkOut

Auf diesen Beitrag antworten »

Ich bin noch nicht so vertraut mit dem Ausruck $\begin{eqnarray*} \max_{k\in(1...2^n)}\left(\frac{1}{1 + \frac{2^n}{k}}\right) \end{eqnarray*}$ , was genau heißt das?

MfG, GetTheFunkOut

29.03.2011, 20:07

wogir

Auf diesen Beitrag antworten »

Ah shit, hab grad n schmarrn geschrieben. Hammer

29.03.2011, 20:14

wogir

Auf diesen Beitrag antworten »

Sorry, wie wärs anders mit der folgenden Abschätzung:

$\begin{eqnarray*} \sum_{k=1}^{2^n} \frac{1}{k+2^n}\geq 2^n\min_{k\in 1...2^n}\left(\frac{1}{k+2^n}\right) \end{eqnarray*}$

wobei $\begin{eqnarray*} \min_{k\in 1...2^n}\left(\frac{1}{k+2^n}\right) \end{eqnarray*}$ halt den kleinsten Wert bezeichnet, den der Ausdruck $\begin{eqnarray*} \left(\frac{1}{k+2^n}\right) \end{eqnarray*}$ annehmen kann.

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen