Vollständige Induktion

14.11.2006, 20:33

lonesome-dreamer

Auf diesen Beitrag antworten »

Vollständige Induktion

Hallo,
ich brüte hier gerade über einer Aufgabe und komme nicht weiter.
Es geht um vollständige Induktion:
$\begin{eqnarray*} \sum^{2^n-1}_{k=1}{\frac{1}{k}}>\frac{n}{2} \end{eqnarray*}$

Jetzt hänge ich beim Induktionsschluss.
$\begin{eqnarray*} n \rightarrow n+1: \sum^{2^{n+1}-1}_{k=1}{\frac{1}{k}}>\frac{n+1}{2} \end{eqnarray*}$
Ich würde jetzt als nächstes die Summe aufspalten. In etwa so:
$\begin{eqnarray*} \sum^{2^n-1}_{k=1}\frac{1}{k}+ \end{eqnarray*}$
Aber wie es hinter dem + weitergehen soll, weiß ich nicht.
Könnte mir bitte jemand einen Tipp geben?

Danke

Gruß
Natalie

14.11.2006, 20:35

Mathespezialschüler

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \sum_{k=1}^{831}~a_k=\sum_{k=1}^{365}~a_k+\sum_{k=366}^{831}~a_k \end{eqnarray*}$ .

Bei dir ist $\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ das, was bei mir $\begin{eqnarray*} 365 \end{eqnarray*}$ ist. Wie heißt dann wohl die nächste Summe?

Gruß MSS

14.11.2006, 20:46

lonesome-dreamer

Auf diesen Beitrag antworten »

Sorry, ich verstehe nicht, was du meinst.
Warum ist bei der zweiten Summe $\begin{eqnarray*} k=2^n \end{eqnarray*}$ ?

14.11.2006, 20:48

Mathespezialschüler

Auf diesen Beitrag antworten »

Ok, nochmal etwas ausführlicher:

$\begin{eqnarray*} \sum_{k=1}^{831}~a_k=a_1+\ldots+a_{365}+a_{366}+\ldots+a_{831} \end{eqnarray*}$

$\begin{eqnarray*} =(a_1+\ldots+a_{365})+(a_{366}+\ldots+a_{831})=\sum_{k=1}^{365}~a_k+\sum_{k=366}^{831}~a_k \end{eqnarray*}$ .

Gruß MSS

14.11.2006, 20:57

lonesome-dreamer

Auf diesen Beitrag antworten »

Ich weiß nicht, auf was du hinauswillst.
Mir ist total unklar, wie du die Summe aufgeteilt hast.

14.11.2006, 20:59

Mathespezialschüler

Auf diesen Beitrag antworten »

Ok ... nochmal etwas kleiner:

$\begin{eqnarray*} \sum_{k=1}^8~a_k=a_1+a_2+a_3+a_4+a_5+a_6+a_7+a_8 \end{eqnarray*}$

$\begin{eqnarray*} =(a_1+a_2+a_3+a_4)+(a_5+a_6+a_7+a_8)=\sum_{k=1}^4~a_k+\sum_{k=5}^8~a_k \end{eqnarray*}$ .

Jetzt verstanden?

Gruß MSS

Anzeige

14.11.2006, 21:04

lonesome-dreamer

Auf diesen Beitrag antworten »

Ja, das letzte Beispiel hab ich verstanden. Aber das erste ist mir immer noch nicht ganz klar. Sollen das willkürliche Zahlenwerte sein, oder hat es einen tieferen Sinn, dass du in der ersten Summe für k=365 gewählt hast?

14.11.2006, 21:23

Mathespezialschüler

Auf diesen Beitrag antworten »

Da habe ich genau das gleiche wie im letzten Beispiel gemacht, nur dass ich anstelle der $\begin{eqnarray*} 4 \end{eqnarray*}$ eine $\begin{eqnarray*} 365 \end{eqnarray*}$ und anstelle der $\begin{eqnarray*} 8 \end{eqnarray*}$ eine $\begin{eqnarray*} 831 \end{eqnarray*}$ gewählt hab. Das sollte nur zur Verdeutlichung sein, deswegen haben $\begin{eqnarray*} 365 \end{eqnarray*}$ und $\begin{eqnarray*} 831 \end{eqnarray*}$ auch nichts mit der Aufgabe zu tun, sondern waren hier willkürlich gewählt.

Gruß MSS

14.11.2006, 21:38

lonesome-dreamer

Auf diesen Beitrag antworten »

Achso, vielen Dank.
Ich glaub dann weiß ich jetzt wie's weitergeht:

$\begin{eqnarray*} \sum^{2^{n+1}-1}_{k=1}{\frac{1}{k}}=\sum^{2^n-1}_{k=1}\frac{1}{k}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\frac{n+1}{2} \end{eqnarray*}$

Stimmt das?

14.11.2006, 22:17

Mathespezialschüler

Auf diesen Beitrag antworten »

Ja. Das musst du beweisen. Jetzt kannst du ja

$\begin{eqnarray*} \sum^{2^n-1}_{k=1}\frac{1}{k}>\frac{n}{2} \end{eqnarray*}$

benutzen.

Gruß MSS

14.11.2006, 22:34

lonesome-dreamer

Auf diesen Beitrag antworten »

Aber wie benutze ich das am besten?
Stünde da ein = müsste ich ja die n/2 in die schon bekannte Summe einsetzen.
Aber wie gehe ich bei einer Ungleichung vor?

14.11.2006, 22:37

Mathespezialschüler

Auf diesen Beitrag antworten »

Naja, jetzt folgt:

$\begin{eqnarray*} \sum^{2^{n+1}-1}_{k=1}{\frac{1}{k}}=\sum^{2^n-1}_{k=1}\frac{1}{k}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}} \end{eqnarray*}$ .

Jetzt musst du noch zeigen, dass gilt:

$\begin{eqnarray*} \frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\frac{n+1}{2} \end{eqnarray*}$ ,

dann bist du fertig.

Gruß MSS

15.11.2006, 10:30

lonesome-dreamer

Auf diesen Beitrag antworten »

Zitat:

Naja, jetzt folgt:

$\begin{eqnarray*} \sum^{2^{n+1}-1}_{k=1}{\frac{1}{k}}=\sum^{2^n-1}_{k=1}\frac{1}{k}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}} \end{eqnarray*}$ .

Wie kommst du auf $\begin{eqnarray*} \frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}} \end{eqnarray*}$ ?

Zitat:

Jetzt musst du noch zeigen, dass gilt:

$\begin{eqnarray*} \frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\frac{n+1}{2} \end{eqnarray*}$

Und das versteh ich leider auch nicht.

15.11.2006, 10:44

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von lonesome-dreamer
Wie kommst du auf $\begin{eqnarray*} \frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}} \end{eqnarray*}$ ?

Schau mal in deine Induktionsvoraussetzung. Die lautet:
$\begin{eqnarray*} \sum^{2^n-1}_{k=1}\frac{1}{k} > \frac{n}{2} \end{eqnarray*}$

Den 1. Summanden kannst du also nach unten mit n/2 abschätzen. Dann hast du:
$\begin{eqnarray*} \frac{n}{2} + \sum^{2^{n+1}-1}_{k=2^n}\frac{1}{k} \end{eqnarray*}$
Jetzt mußt du zeigen, daß dieses größer als $\begin{eqnarray*} \frac{n+1}{2} \end{eqnarray*}$ ist.
Dazu schätze wie folgt ab:
$\begin{eqnarray*} \frac{1}{k} > \frac{1}{2^{n+1}} \end{eqnarray*}$

15.11.2006, 17:19

lonesome-dreamer

Auf diesen Beitrag antworten »

Also, ich hab's echt nicht drauf. unglücklich

unglücklich

Zitat:

Den 1. Summanden kannst du also nach unten mit n/2 abschätzen. Dann hast du:
$\begin{eqnarray*} \frac{n}{2} + \sum^{2^{n+1}-1}_{k=2^n}\frac{1}{k} \end{eqnarray*}$

Das bedeutet ja, dass man $\begin{eqnarray*} \sum^{2^n-1}_{k=1}\frac{1}{k} \end{eqnarray*}$ mit $\begin{eqnarray*} \frac{n}{2} \end{eqnarray*}$ gleichsetzt. Aber das ist doch eine Ungleichung.

Zitat:

Dazu schätze wie folgt ab:
$\begin{eqnarray*} \frac{1}{k} > \frac{1}{2^{n+1}} \end{eqnarray*}$

Und das kann ich auch nicht nachvollziehen.

15.11.2006, 17:30

Mathespezialschüler

Auf diesen Beitrag antworten »

Ich habe das ja auch nicht gleich gesetzt!

Zitat:

Original von Mathespezialschüler
Naja, jetzt folgt:

$\begin{eqnarray*} \sum^{2^{n+1}-1}_{k=1}{\frac{1}{k}}=\sum^{2^n-1}_{k=1}\frac{1}{k}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}} \end{eqnarray*}$ .

Wir wollen zeigen, dass $\begin{eqnarray*} a>c \end{eqnarray*}$ gilt, wobei $\begin{eqnarray*} a=\sum^{2^{n+1}-1}_{k=1}{\frac{1}{k}} \end{eqnarray*}$ und $\begin{eqnarray*} c=\frac{n+1}{2} \end{eqnarray*}$ ist. Wir wissen dass $\begin{eqnarray*} a>b \end{eqnarray*}$ ist, $\begin{eqnarray*} b=\frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}~{\frac{1}{k}} \end{eqnarray*}$ . Wenn du jetzt zeigen kannst, dass $\begin{eqnarray*} b>c \end{eqnarray*}$ ist, dann folgt wegen $\begin{eqnarray*} a>b \end{eqnarray*}$ :

$\begin{eqnarray*} a>c \end{eqnarray*}$ .

Und dann bist du fertig. Deswegen machen wir das überhaupt ...

Gruß MSS

15.11.2006, 17:47

lonesome-dreamer

Auf diesen Beitrag antworten »

Aha, jetzt versteh ich.
Und um $\begin{eqnarray*} \frac{n}{2}+\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\frac{n+1}{2} \end{eqnarray*}$
zu zeigen, braucht man diese Abschätzung: $\begin{eqnarray*} \frac{1}{k} > \frac{1}{2^{n+1}} \end{eqnarray*}$ .
Aber wie kommt man darauf, dass $\begin{eqnarray*} k>2^{n+1} \end{eqnarray*}$ ?

15.11.2006, 18:00

Mathespezialschüler

Auf diesen Beitrag antworten »

Es gilt $\begin{eqnarray*} k<2^{n+1} \end{eqnarray*}$ !! Denn das ist äquivalent zu $\begin{eqnarray*} \frac{1}{k}>\frac{1}{2^{n+1}} \end{eqnarray*}$ !

$\begin{eqnarray*} a>b>0\Leftrightarrow 0<\frac{1}{a}<\frac{1}{b} \end{eqnarray*}$

Gruß MSS

15.11.2006, 18:21

lonesome-dreamer

Auf diesen Beitrag antworten »

OK, Leichtsinnsfehler.

Aber wie kommt man denn nun auf diese Beziehung?

15.11.2006, 18:28

Mathespezialschüler

Auf diesen Beitrag antworten »

Naja, $\begin{eqnarray*} k \end{eqnarray*}$ ist ja der Laufindex und der läuft von $\begin{eqnarray*} 2^n \end{eqnarray*}$ bis $\begin{eqnarray*} 2^{n+1}-1 \end{eqnarray*}$ , also gilt $\begin{eqnarray*} 2^n\leq k\leq 2^{n+1}-1 \end{eqnarray*}$ und daraus folgt:

$\begin{eqnarray*} k<2^{n+1} \end{eqnarray*}$ .

Gruß MSS

15.11.2006, 18:50

lonesome-dreamer

Auf diesen Beitrag antworten »

Eins ist mir aber immer noch nicht ganz klar. Wieso kann man daraus $\begin{eqnarray*} 2^n\leq k\leq 2^{n+1}-1 \end{eqnarray*}$ das $\begin{eqnarray*} k<2^{n+1} \end{eqnarray*}$ folgern?

15.11.2006, 19:01

Mathespezialschüler

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} a=2^{n+1} \end{eqnarray*}$ . Dann gilt also (s.o.):

$\begin{eqnarray*} k\leq a-1 \end{eqnarray*}$ .

Und da $\begin{eqnarray*} a-1<a \end{eqnarray*}$ ist, folgt:

$\begin{eqnarray*} k<a=2^{n+1} \end{eqnarray*}$ .

Gruß MSS

15.11.2006, 19:17

lonesome-dreamer

Auf diesen Beitrag antworten »

Dankeschön.
Jetzt ist's klar.

Aber wieder zurück zum Eigentlichen:
Mit dieser Abschätzung an sich kann ich nicht viel anfangen. Ich weiß nämlich 1. nicht, wie man darauf kommt und 2. was man mit ihr dann anfängt.

15.11.2006, 19:23

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von lonesome-dreamer
Mit dieser Abschätzung an sich kann ich nicht viel anfangen. Ich weiß nämlich 1. nicht, wie man darauf kommt und 2. was man mit ihr dann anfängt.

Ich dachte, das erste hätten wir gerade besprochen?! Zum zweiten: Die Abschätzung einfach auf die Summe anwenden und anschließend die entstehende Summe ausrechnen.

Gruß MSS

15.11.2006, 19:28

lonesome-dreamer

Auf diesen Beitrag antworten »

Zitat:

Ich dachte, das erste hätten wir gerade besprochen?!

Ja schon. Aber mir ist nicht klar, warum man das machen muss.

15.11.2006, 19:38

Mathespezialschüler

Auf diesen Beitrag antworten »

Man muss das nicht machen, man kann. Und das tut man eben, weil es hier beim Beweis hilft. Inwiefern es hilft, wirst du dann schon noch sehen. Augenzwinkern

Augenzwinkern

Gruß MSS

15.11.2006, 19:39

lonesome-dreamer

Auf diesen Beitrag antworten »

Ok, und wie geht es damit dann weiter?
Ich habe nämlich gerade keinen Plan, was ich mit dieser Abschätzung anfangen soll.

15.11.2006, 20:03

klarsoweit

Auf diesen Beitrag antworten »

Setze die Abschätzung für k in die Summe ein und berechne sie:

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

15.11.2006, 20:10

lonesome-dreamer

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{k}}>\sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{2^{n+1}}} \end{eqnarray*}$
So? Und wie geht's dann weiter?

15.11.2006, 20:18

Mathespezialschüler

Auf diesen Beitrag antworten »

Du hast jetzt eine Summe der Form

$\begin{eqnarray*} \sum_{k=a}^b~c \end{eqnarray*}$ .

Hängt $\begin{eqnarray*} c \end{eqnarray*}$ dabei von $\begin{eqnarray*} k \end{eqnarray*}$ ab? Was ist das Ergebnis der Summe?

Gruß MSS

15.11.2006, 20:24

lonesome-dreamer

Auf diesen Beitrag antworten »

Zitat:

Hängt $\begin{eqnarray*} c \end{eqnarray*}$ dabei von $\begin{eqnarray*} k \end{eqnarray*}$ ab?

Nein.
Dann ist
$\begin{eqnarray*} \sum^{2^{n+1}-1}_{k=2^n}{\frac{1}{2^{n+1}}}={\frac{1}{2^{n+1}}} \end{eqnarray*}$ ?

15.11.2006, 20:38

Mathespezialschüler

Auf diesen Beitrag antworten »

Nein! Du addierst eine Konstante auf, aber doch nicht nur einmal! Wie viele Summanden sind denn das?

Gruß MSS

15.11.2006, 20:42

lonesome-dreamer

Auf diesen Beitrag antworten »

Zitat:

Wie viele Summanden sind denn das?

$\begin{eqnarray*} 2^{n+1}-1-2^n \end{eqnarray*}$ ?

15.11.2006, 20:45

Mathespezialschüler

Auf diesen Beitrag antworten »

Nicht ganz. Du fängst ja bei $\begin{eqnarray*} 2^n \end{eqnarray*}$ an und hörst bei $\begin{eqnarray*} 2^{n+1}-1 \end{eqnarray*}$ auf. Mal ein Beispiel: Wenn du bei $\begin{eqnarray*} 8 \end{eqnarray*}$ anfängst und bei $\begin{eqnarray*} 15 \end{eqnarray*}$ aufhörst, wie viele Summanden sind das dann?

$\begin{eqnarray*} \sum_{k=8}^{15}~c=\underbrace{c}_{k=8}+\underbrace{c}_{k=9}+\underbrace{c}_{k=10}+\underbrace{c}_{k=11}+\underbrace{c}_{k=12}+\underbrace{c}_{k=13}+\underbrace{c}_{k=14}+\underbrace{c}_{k=15} \end{eqnarray*}$

Gruß MSS

15.11.2006, 20:52

lonesome-dreamer

Auf diesen Beitrag antworten »

Ah. Ok, dann so:
$\begin{eqnarray*} 2^{n+1}-1-2^n+1 \end{eqnarray*}$

15.11.2006, 20:54

Mathespezialschüler

Auf diesen Beitrag antworten »

Jap! Das ist ja $\begin{eqnarray*} =2^{n+1}-2^n=2\cdot 2^n-2^n=2^n \end{eqnarray*}$ . Was ist dann die gesuchte Summe $\begin{eqnarray*} \sum_{k=2^n}^{2^{n+1}-1}~\frac{1}{2^{n+1}} \end{eqnarray*}$ ?

Gruß MSS

15.11.2006, 21:01

lonesome-dreamer

Auf diesen Beitrag antworten »

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

15.11.2006, 21:08

Mathespezialschüler

Auf diesen Beitrag antworten »

Genau. Jetzt nochmal alles zusammenfügen und dann bist du fertig. smile

smile

Gruß MSS

15.11.2006, 21:17

lonesome-dreamer

Auf diesen Beitrag antworten »

Meinst du mit "zusammenfügen", dass die $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ zur Induktionsvoraussetzung dazu addiert werden müssen?

15.11.2006, 21:20

Mathespezialschüler

Auf diesen Beitrag antworten »

Mit "Zusammenfügen" meine ich, dass du alles nochmal aufschreibst und das, was wir jetzt alles hergeleitet haben, benutzt, um den Induktionsschluss zu beenden. Augenzwinkern

Augenzwinkern

Gruß MSS

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »