komme bei vollständiger Induktion nicht weiter

26.01.2012, 12:00

Peckham

komme bei vollständiger Induktion nicht weiter

Hi,

Ich versuche schon seit längerem folgenden Beweis mittels vollständiger Induktion zu erbringen, aber ich komme einfach nicht drauf, wie ich richtig umforme.
Das eigentliche Prinzip der vollst. Ind. ist mir aber klar.

\sum_{k=1}^{2^n} 1/k >= 1+ (n/2)

Hoffe die Aufgabenstellung wird klar, da das Summenzeichen nicht funktioniert unglücklich

Es soll heißen: die Summe von k=1 bis 2^n über 1/k ist größer/gleich 1+ (n/2)

Ich habe schon versucht die Ungleichung vorher umzuschreiben aber das bringt mich auch nicht richtig weiter, darf ich das überhaupt?

Wäre sehr froh wenn mir hier jemand den entscheidenden Tipp geben könnte

Danke

26.01.2012, 12:10

Helferlein

Auf diesen Beitrag antworten »

Das funktioniert schon, nur muss das Board wissen, dass es sich um Latex-Code handelt.
Wenn Du es noch schöner formatieren willst, nimm diese Eingabe:

code:
1:	[latex] \sum_{k=1}^{2^n} \frac 1k \geq 1+ \frac n2[/latex]

Das sieht dann so aus:
$\begin{eqnarray*} \sum_{k=1}^{2^n} \frac 1k \geq 1+ \frac n2 \end{eqnarray*}$

Zum Beweis: Du bist hoffentlich soweit gekommen

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

Jetzt musst Du Dir nur noch überlegen, weshalb die letzte Summe größer als 0,5 sein muss.

26.01.2012, 12:35

Peckham

Auf diesen Beitrag antworten »

Vielen Dank schonmal

ja soweit war ich, die letzte Summe kann ich doch aber umschreiben zu:

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

und das ist ja immer kleiner als 0,5

und ich verstehe auch nicht warum du diesen Summanden noch mal auf der rechten Seite der Ungleichung dazu addiert hast?
Man zieht doch nur auf der linken Seite die Summe auseinander

26.01.2012, 13:06

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Peckham
ja soweit war ich, die letzte Summe kann ich doch aber umschreiben zu:

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

Nein, das ist doch nur der allerletzte Summand dieser Summe. Und es geht auch nicht darum, dass dieser Summand kleiner als 0,5 ist, sondern dass die gesamte letztere Summe größer als 0,5 ist!

So richtig scheinst du noch nicht verstanden zu haben, was Helferlein da im Induktionsschritt begonnen hat. unglücklich

26.01.2012, 13:37

Peckham

Auf diesen Beitrag antworten »

ne das von Helferlein verstehe ich echt nicht.

Man spaltet den letzten Summanden ab, aber warum steht hinter dem $\begin{eqnarray*} \geq \end{eqnarray*}$ nicht $\begin{eqnarray*} \frac{n+1}{2} \end{eqnarray*}$

Das die Summe hinter dem $\begin{eqnarray*} \geq \end{eqnarray*}$ größer als 0,5 ist, ist mir klar aber das bringt mich nicht weiter

26.01.2012, 14:37

Helferlein

Auf diesen Beitrag antworten »

Nich böse gemeint, aber anscheinend gehörst Du auch zu den Studenten, die beide Seiten ziellos solange umformen, bis sich die Terme irgendwann in der Mitte treffen.

Bei der Induktion musst Du die Gleichung für n+1 zeigen und dabei nutzen, dass die Gleichung für n gültig ist. Ich habe im Schritt oben die Summe so auseinander gezogen, dass wir die Summe für n darin wiederfinden, um die Induktionsvoraussetzung zu nutzen. Im zweiten Schritt habe ich genau diese Voraussetzung dann genutzt, weshalb da $\begin{eqnarray*} 1+\frac n2 \end{eqnarray*}$ steht.
Du musst nun diesen Term weiter umformen oder abschätzen, bis Du ganz am Ende den Term $\begin{eqnarray*} \frac{n+1}2 \end{eqnarray*}$ herausbekommen.

26.01.2012, 17:16

Peckham

Auf diesen Beitrag antworten »

wie du auf die Ungleichung in deinem ersten Beitrag kommst habe ich jetzt verstanden. Muss ich als nächstes 0,5 auf beiden Seiten addieren? Dann hätte ich die Ungleichung doch eigentlich schon bewiesen oder?

Die Aufgabe treibt mich echt in den Wahnsinn

27.01.2012, 01:49

Helferlein

Auf diesen Beitrag antworten »

Irgendwie hast Du anscheinend immer noch nicht verstanden, wie man Induktionsbeweise führen sollte. Es wird nie auf beiden Seiten addiert/subtrahiert oder sonstwas gemacht, sondern man arbeitet sich immer von der linken zur rechten Seite vor.

Wir waren bei

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

Unser Ziel ist es, die rechte Seite auf die Form $\begin{eqnarray*} 1+\frac{n+1}2 \end{eqnarray*}$ bzw. $\begin{eqnarray*} 1+\frac n2 + \frac 12 \end{eqnarray*}$ zu bringen.

Den ersten Teil haben wir schon. Für den zweiten musst Du zeigen, dass $\begin{eqnarray*} \sum_{k=2^n+1}^{2^{n+1}} \frac 1k \geq \frac 12 \end{eqnarray*}$

27.01.2012, 14:34

Peckham

Auf diesen Beitrag antworten »

so langsam kapiere ich es immer mehr... ich mache jetzt mal ab dem letzten Schritt weiter

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

bei den letzten beiden Summentermen setzte ich n=1 da es ja das kleinste n ist das ich einsetzen darf

$\begin{eqnarray*} \geq 1+\frac{n}{2} +1+\frac{1}{2} +\frac{1}{3} +\frac{1}{4} -(1+\frac{1}{2}) \geq 1+\frac{1+n}{2} +\frac{1}{12} \end{eqnarray*}$

stimmt das jetzt???

27.01.2012, 17:17

Helferlein

Auf diesen Beitrag antworten »

Nein, leider immer noch nicht.
n=1 ist zwar das kleinste n, aber woher weisst Du, dass n=1 auch die kleinste Differenz der letzten Summenterme ergibt?

Schau Dir eher die Anzahl der Summanden in der zu bestimmenden Summe an und schätze diese ab.

27.01.2012, 20:47

Peckham

Auf diesen Beitrag antworten »

ok ich glaube jetzt habe ich es aber wirklich... mein Fehler war die ganze zeit, dass ich die letzte Summe von 2^(n+1) bis 2^(n+1) gehen ließ. Damit habe ich natürlich einen ganzen Haufen Summenglieder verloren.

Die Summe, die ja bei 2^(n)+1 beginnt, schätze ich nach unten ab, also mit dem kleinsten Summanden nämlich $\begin{eqnarray*} \frac{1}{2^{n+1} } \end{eqnarray*}$

Dann überlege ich wieviele Summanden ich in meiner Summe habe, nämlich nicht nur einen wie ich die ganze Zeit dachte sondern $\begin{eqnarray*} 2^{n} \end{eqnarray*}$

Durch Kürzen komme ich dann genau auf 0,5.

So stimmt das doch jetzt aber???

28.01.2012, 01:51

Helferlein

Auf diesen Beitrag antworten »

Was lange währt, wird endlich gut smile