Problem bei vollst.Induktion

25.04.2005, 19:56

Mario25

Problem bei vollst.Induktion

Hi,
bei meinem letzten Post hat keiner so recht verstanden wo mein Problem liegt, deshalb probier ich es nochmal auf seite 1 erneut.

Es soll eine Vollständige Induktion auf folgendes durchgeführt werden:

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

Mein Ansatz :

aus $\begin{eqnarray*} \sum_{k=1}^{2^n}~ \frac{1}{k} \geq 1+\frac{n}{2} \end{eqnarray*}$

muss auch $\begin{eqnarray*} \sum_{k=1}^{2^{n+1}}~ \frac{1}{k} \geq 1+\frac{n+1}{2} \end{eqnarray*}$ folgen..

Beweis: $\begin{eqnarray*} \sum_{k=1}^{2^{n+1}}~ \frac{1}{k} = \sum_{k=1}^{2^n}~ \frac{1}{k} + \sum_{k=2^n}^{2^{n+1}}~ \frac{1}{k} \end{eqnarray*}$

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

ja und nun komm ich nicht weiter ..... vielleicht versteht jemand mein problem ....es ist nämlich

$\begin{eqnarray*} \sum_{k=1}^{2^{n+1}}~ \frac{1}{k} \neq \sum_{k=1}^{2^n}~\frac{1}{k} + \sum_{k=2^{n+1}}^{2^{n+1}}~ \frac{1}{k} \end{eqnarray*}$

Gibt es eine Mögl wie ich es anstellen könnte???

25.04.2005, 20:56

martins1

Auf diesen Beitrag antworten »

Induktionsannahme
$\begin{eqnarray*} \sum_{k=1}^{2^n}~\frac{1}{k}\geq 1+\frac{n}{2} \end{eqnarray*}$
Dann gilt
$\begin{eqnarray*} \sum_{k=1}^{2^{n+1}}~\frac{1}{k}=\sum_{k=1}^{2^n}~\frac{1}{k}+\sum_{k=2^n}^{2^{n+1}}~\frac{1}{k}\geq 1+\frac{n}{2}+\sum_{k=2^n}^{2^{n+1}}~\frac{1}{2^{n+1}}=1+\frac{n}{2}+\frac{2^n}{2^{n+1}}=1+\frac{n}{2}+\frac{1}{2}=1+\frac{n+1}{2} \end{eqnarray*}$
Und somit ist der Induktionsschritt vollzogen worden.

25.04.2005, 21:22

Mario25

Auf diesen Beitrag antworten »

Problem ....

$\begin{eqnarray*} 1+\frac{n}{2}+\sum_{k=2^n}^{2^{n+1}}~\frac{1}{2^{n+1}} \end{eqnarray*}$

der Schritt kann doch gar nicht stimmen .... wie will ich ne summe von 1/2^(n+1) machen wenn die summe insgesamt nur von k abhängig ist.

Dein Schritt ist mir vollkommen unklar. Das diese Summe dann 1/2 ergeben muss leuchtet mir ein aber dein Rechenweg kann nicht korrekt sein! oder?

25.04.2005, 21:49

Auf diesen Beitrag antworten »

Zitat:

Original von Mario25
$\begin{eqnarray*} 1+\frac{n}{2}+\sum_{k=2^n}^{2^{n+1}}~\frac{1}{2^{n+1}} \end{eqnarray*}$

der Schritt kann doch gar nicht stimmen

Unfug - der Schritt stimmt "fast": Es wird über eine Konstante (bzgl. k) summiert, und die Summe über eine Konstante ist gleich der Konstanten mal Anzahl der Summenglieder, hier also

$\begin{eqnarray*} \sum_{k=2^n+1}^{2^{n+1}}~\frac{1}{2^{n+1}}= \frac{1}{2^{n+1}}\cdot\left(2^{n+1}-2^n\right)=\frac{2^n}{2^{n+1}}=\frac{1}{2} \end{eqnarray*}$

Das "fast" deshalb: Die Summation beginnt erst bei $\begin{eqnarray*} 2^n+1 \end{eqnarray*}$ , und nicht schon bei $\begin{eqnarray*} 2^n \end{eqnarray*}$ .

25.04.2005, 22:09

Mario25

Auf diesen Beitrag antworten »

gut wenn dus so definierst isses ja logisch aber wenn ich das so mache von k=2^(n+1) bis 2^(n+1) was ist dann mit den summen zwischen 2^n und 2^(n+1) was ich ganz oben als mein problem ausgewiesen habe????

25.04.2005, 22:17

Mario25

Auf diesen Beitrag antworten »

ach ja es heißt ja hier 2^n +1 gut gut .... das macht das Formelprogramm ein wenig schlecht leserlich. Gut danke für eure hilfe jetzt ist alles klar!!!!

26.04.2005, 14:41

Mario25

Auf diesen Beitrag antworten »

Also ich noch mal ... hab heute probiert eure Rechnung zu verstehen doch da macht einiges wirklich keinen Sinn.

1. Problem

$\begin{eqnarray*} \sum_{k=2^n+1}^{2^{n+1}}~\frac{1}{2^{n+1}} \end{eqnarray*}$

Wieso kann man das $\begin{eqnarray*} \frac{1}{k} \end{eqnarray*}$ einfach durch eine Konstante Ersetzen.

2.Problem ... Meine Aufgabe ging noch weiter .... es sollte ebenfalls gegeben sein das

$\begin{eqnarray*} \sum_{k=1}^{2^{n}}~ \frac{1}{k} \leq n+\frac{1}{2} \end{eqnarray*}$

mach ich es genauso wie mit eurer Rechnung oben komm ich auf

$\begin{eqnarray*} \sum_{k=1}^{2^{n}}~ \frac{1}{k} + \sum_{k={2^{n}+1}}^{2^{n+1}}~ \frac{1}{2^{n+1}} \leq n+\frac{1}{2} + \frac{1}{2} \neq n+1+\frac{1}{2} \end{eqnarray*}$

wo liegt jetzt schon wieder mein Denkfehler???

26.04.2005, 14:56

klarsoweit

Auf diesen Beitrag antworten »

Es geht offensichtlich um den Ausdruck:
$\begin{eqnarray*} \sum_{k=2^n + 1}^{2^{n+1}}~\frac{1}{k} \end{eqnarray*}$
Nun: Das k läuft von 2^n + 1 aufwärts bis 2^(n+1). Man kann also die Summe nach unten abschätzen, indem man für jedes 1/k den Term 1/2^(n+1) schreibt. Also:
$\begin{eqnarray*} \sum_{k=2^n + 1}^{2^{n+1}}~\frac{1}{k} \geq \sum_{k=2^n + 1}^{2^{n+1}}~\frac{1}{2^{n+1}} \end{eqnarray*}$
Das sind insgesamt 2^(n+1) - 2^n Summanden. Also:
$\begin{eqnarray*} \sum_{k=2^n + 1}^{2^{n+1}}~\frac{1}{2^{n+1}} = (2^{n+1} - 2^n) \cdot \frac{1}{2^{n+1}} = \frac{2^n}{2^{n+1}} = \frac{1}{2} \end{eqnarray*}$
Ich denke, der Rest ist dann klar.

Beim 2. Problem brauchst du vermutlich eine andere Abschätzung (nach oben). Schreib deine Rechnung mal hin.

26.04.2005, 15:14

Auf diesen Beitrag antworten »

@klarsoweit

Das ist ein Fehler, der sich von martins1' Induktionsbeweis bis hierher schleppt: $\begin{eqnarray*} k=2^n \end{eqnarray*}$ ist schon verbraten, die Summe muss bei $\begin{eqnarray*} k=2^n+1 \end{eqnarray*}$ starten.

26.04.2005, 15:17

klarsoweit

Auf diesen Beitrag antworten »

Stimmt.

Habs auch gerade gemerkt. Ich werde es bei mir korrigieren.

Neue Frage »

Antworten »

Problem bei vollst.Induktion

Verwandte Themen