Vollständige Induktion

20.10.2013, 23:34

Shattered

Vollständige Induktion

Guten Abend,

ich sitze jetzt schon ein Weilchen an einer Aufgabe, komme jedoch nicht zu einer entsprechenden Lösung.

Es ist zu beweisen, dass

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

für n $\begin{eqnarray*} \in\mathbb N \end{eqnarray*}$ gilt.

Mit meinem Ansatz bin ich bis

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

gekommen. Sollte ich nun fertig sein, würde ich gerne wissen warum. Wenn ein Fehler enthalten sein sollte, kann ich auch meinen kompletten Ansatz posten, oder andernfalls würde ich auch Hinweise sehr gerne entgegennehmen.

Gruß Shattered

20.10.2013, 23:58

Lithiesque

Auf diesen Beitrag antworten »

Etwas ausführlicher wäre ganz schön, denn was du da hingeschrieben hast, ist nicht einmal eine Aussage (und sieht abgesehen davon nicht besonders zielführend aus). Vielleicht schreibst du erst mal hin, was genau im Induktionsschluss zu zeigen ist.

21.10.2013, 00:27

Shattered

Auf diesen Beitrag antworten »

Gut, die Aufgabe besteht darin per vollständiger Induktion zu zeigen, dass die oben genannte Gleichung korrekt ist. Den Beweis führe ich mit einer Induktion nach n durch.

Für den Induktionsansatz betrachte ich den Fall n=1:

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

Damit wäre die Induktionsverankerung gesetzt. Die Induktionsvoraussetzung ist durch

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

gegeben. Dies gelte nun für ein beliebiges, aber festes n $\begin{eqnarray*} \in\mathbb N \end{eqnarray*}$ . Dann folgt:

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

Ich gehe nun so vor:

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

Hier nutze ich eine Indexverschiebung.

= $\begin{eqnarray*} \sum_{k=0}^{n} \end{eqnarray*}$ $\begin{eqnarray*} \frac{1}{((n+1)+k)-1} \end{eqnarray*}$

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

Nun nutze ich die Induktionsvoraussetzung und komme auf:

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

Hier bin ich dann auch mit meinem Latein am Ende, um Hilfe wird gebeten.

Gruß Shattered

21.10.2013, 00:55

Lithiesque

Auf diesen Beitrag antworten »

Zitat:

Original von Shattered
Hier nutze ich eine Indexverschiebung.

= $\begin{eqnarray*} \sum_{k=0}^{n} \end{eqnarray*}$ $\begin{eqnarray*} \frac{1}{((n+1)+k)-1} \end{eqnarray*}$

Falsch. Es ist $\begin{eqnarray*} \sum_{k=1}^{n+1} \end{eqnarray*}$ $\begin{eqnarray*} \frac{1}{(n+1)+k} = \sum_{k=0}^{n} \end{eqnarray*}$ $\begin{eqnarray*} \frac{1}{(n+1)+k+1} \end{eqnarray*}$ . Du müsstest, um $\begin{eqnarray*} n+k \end{eqnarray*}$ im Nenner zu erhalten, den Index schon "in die andere Richtung" schieben, d.h. so, dass $\begin{eqnarray*} k \end{eqnarray*}$ von $\begin{eqnarray*} 2 \end{eqnarray*}$ bis $\begin{eqnarray*} n+2 \end{eqnarray*}$ läuft.

21.10.2013, 01:21

Shattered

Auf diesen Beitrag antworten »

Super, vielen Dank!
Nun komme ich auf:

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

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

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

Und 'von der anderen Seite' komme ich bis:

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

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

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

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

Mir ist hierbei klar, dass $\begin{eqnarray*} (-1)^{(2n+2)+1} \end{eqnarray*}$ immer negativ und $\begin{eqnarray*} (-1)^{(2n+1)+1} \end{eqnarray*}$ stets positiv sein muss. Mein Rechenweg setzt natürlich auch voraus, dass ich bei $\begin{eqnarray*} \sum_{k=1}^{2(n+1)} \end{eqnarray*}$ 2*(n+1) vor dem verrechnen ausgeklammert habe, da ich mir anders nicht zu helfen wusste.
Und hier bin ich wieder (leider) am Festsitzen.

Gruß Shattered

21.10.2013, 01:37

Lithiesque

Auf diesen Beitrag antworten »

Am besten bleibst du mal bei einer "Seite"; wenn man sich nicht verrechnet, kommt man da nämlich ganz gut durch.

Zitat:

Original von Shattered
$\begin{eqnarray*} \sum_{k=1}^{n+1} \end{eqnarray*}$ $\begin{eqnarray*} \frac{1}{(n+1)+k} \end{eqnarray*}$ = $\begin{eqnarray*} \sum_{k=1}^{n} \end{eqnarray*}$ $\begin{eqnarray*} \frac{1}{n+k} \end{eqnarray*}$ + $\begin{eqnarray*} \frac{1}{n+k+2} \end{eqnarray*}$ + $\begin{eqnarray*} \frac{1}{n+k+1} \end{eqnarray*}$ + $\begin{eqnarray*} \frac{1}{n+2} \end{eqnarray*}$

Das stimmt nicht. Es ist $\begin{eqnarray*} \sum_{k=1}^{n+1} \end{eqnarray*}$ $\begin{eqnarray*} \frac{1}{(n+1)+k} = \sum_{k=2}^{n+2} \frac{1}{n+k} = \sum_{k=1}^n \frac{1}{n+k} + A(n) \end{eqnarray*}$ , wobei $\begin{eqnarray*} A(n) \end{eqnarray*}$ ein (nur) von $\begin{eqnarray*} n \end{eqnarray*}$ abhängender Term ist, der dafür sorgt, dass eine wahre Behauptung da steht. Du müsstest nun zuerst diesen Term bestimmen und dann noch ein kleines bisschen überlegen/rechnen, um zum Ende des Induktionsschlusses zu kommen.

Was du zum Herangehen von der anderen Seite gerechnet hast, ist korrekt, läuft aber im Grunde auf dasselbe hinaus wie das Weiterverfolgen des ersten Ansatzes.

21.10.2013, 01:54

Shattered

Auf diesen Beitrag antworten »

Diesen Ansatz habe ich schon einmal gesehen, aber ich habe nicht wirklich verstanden wie man auf diesen Term kommt. Wenn es nicht zu viel gefragt ist, würde ich dich doch gerne bitten kurz zu erklären, wie man auf diesen Term kommt. (Darauf schließend, dass es der selbe Term sein muss wie 'von der anderen Seite' aus, müsste es ja

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

lauten.)

Gruß Shattered

21.10.2013, 02:32

Lithiesque

Auf diesen Beitrag antworten »

Ok, du gehst aus von $\begin{eqnarray*} \sum_{k=2}^{n+2} \frac{1}{n+k} \end{eqnarray*}$ und willst zu einem Ausdruck, der $\begin{eqnarray*} \sum_{k=1}^n \frac{1}{n+k} \end{eqnarray*}$ beinhaltet (um die Induktionsvoraussetzung anwenden zu können). Diese beiden Summen stimmen schon im Wesentlichen überein; allerdings fehlen in der zweiten Summe die beiden Summanden mit $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ und $\begin{eqnarray*} k=n+2 \end{eqnarray*}$ ; diese beiden muss man also, um einen Schritt in Richtung Gleichheit zu tun, noch zur zweiten Summe addieren.
Der zweite Unterschied ist, dass man bei der zweiten Summe den Summanden mit $\begin{eqnarray*} k=1 \end{eqnarray*}$ , der bei der ersten Summe nicht vorhanden ist, addiert - den muss man also von der zweiten Summe wieder abziehen.

Das führt auf $\begin{eqnarray*} \sum_{k=2}^{n+2} \frac{1}{n+k} = \sum_{k=1}^n \frac{1}{n+k} + \frac{1}{2n+1} + \frac{1}{2n+2} - \frac{1}{n+1} \end{eqnarray*}$ . Jetzt die Induktionsvoraussetzung anwenden, und dann ein bisschen schauen, welche Schritte zum Ziel noch fehlen.

21.10.2013, 02:43

Shattered

Auf diesen Beitrag antworten »

Jap! Denn wenn man 1/(2n+1) + (1/(2n+2) - 1/(n+1)) zuerst rechnet, erhält man 1/(2n+1)-1/(2n+2), was deckungsgleich ist mit der obrigen Formel, beziehungsweise der 'anderen Seite'.
Verzeih mir die saloppe Schreibweise, aber es ist doch recht spät, und ich freue mich, dass du dir die Zeit genommen hast es mir zu erklären. Insgesamt alles sehr verständlich und ich hoffe, dass ich diese Vorgehensweise auch zukünftig im Kopf behalten werde.

Vielen Dank für die nette Hilfe!

Gruß Shattered

21.10.2013, 13:03

Grautvornix

Auf diesen Beitrag antworten »

Und alternativ ohne Induktion:

Offenbar gilt

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

und andererseits gilt auch

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

Damit folgt schon die Behauptung. Fertig!

21.10.2013, 13:57

jimmyt

Auf diesen Beitrag antworten »

Das kann ich nicht bestätigen. Bei beiden Gleichungen klappt die vollständige Induktion nicht. I.A. ist kein Problem, aber I.S. geht nicht auf.
Bspw. bekomme ich bei der zweiten Gleichung im I.S.:

$\begin{eqnarray*} \text{I.V.} \quad \sum_{k=1}^{n} \frac{1}{n+k} = \sum_{k=1}^{2n} \frac{1}{k} - \sum_{k=1}^{n} \frac{1}{k} \end{eqnarray*}$

$\begin{eqnarray*} \text{I.S.} \quad \text{zu zeigen:} \; \sum_{k=1}^{n+1} \frac{1}{n+1+k} = \sum_{k=1}^{2n+2} \frac{1}{k} - \sum_{k=1}^{n+1} \frac{1}{k} \end{eqnarray*}$

$\begin{eqnarray*} \text{Vorüberlegung:} \quad \sum_{k=1}^{n+1} \frac{1}{n+1+k} = \sum_{k=2}^{n+2} \frac{1}{n+k}= \left ( \sum_{k=1}^{n} \frac{1}{n+k} \right ) + \frac{1}{2n+1} - \frac{1}{2n+2} \end{eqnarray*}$

$\begin{eqnarray*} n \Rightarrow n+1: \end{eqnarray*}$

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

$\begin{eqnarray*} \stackrel{I.V.}{=} \left ( \sum_{k=1}^{2n} \frac{1}{k} - \sum_{k=1}^{n} \frac{1}{k} \right ) + \frac{1}{2n+1} - \frac{1}{2n+2} \end{eqnarray*}$

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

Aber mein I.S. kann auch falsch sein.
Es wäre nett, wenn du deine beiden Gleichungen beweisen könntest. Danke dir im Voraus. Augenzwinkern

*********************************************************************

Sorry, [die Darstellung von Grautvornix] stimmt doch! smile

*********************************************************************

wegen:

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

edit von sulo: 2 Vollzitate entfernt, 3 Mehrfachposts zusammengefügt. Eine Einfügung für das Verständnis platziert.
Bitte informiere dich mal im Boardprinzip, wie Beiträge verfasst werden sollen.
Vielen Dank.

21.10.2013, 14:14

Guppi12

Auf diesen Beitrag antworten »

@jimmyt:

Du musst ja auch nicht alles mit Induktion beweisen. Ich nehme mal an, Grautvornix hat diese Gleichungen hingeschrieben, weil es mit denen eben auch ohne Induktion geht und man sich so viel Zeit spart.

Dass jene Gleichungen stimmt, sieht man eigentlich auch so Augenzwinkern

21.10.2013, 14:24

jimmyt

Auf diesen Beitrag antworten »

Zitat:

Original von Guppi12
... Dass jene Gleichungen stimmt, sieht man eigentlich auch so Augenzwinkern

Da hast du aber ein gutes Auge. Augenzwinkern

21.10.2013, 14:48

Guppi12

Auf diesen Beitrag antworten »

Nunja, ich versuche mal, es zu erklären:

In der ersten Gleichung steht eigentlich folgendes:

Links werden die Kehrwerte der ersten $\begin{eqnarray*} 2n \end{eqnarray*}$ Zahlen addiert. Dabei treten allerdings jene von geraden Zahlen mit negativem Vorzeichen auf. Also werden eigentlich die Kehrwerte der ungeraden Zahlen zwischen $\begin{eqnarray*} 1 \end{eqnarray*}$ und $\begin{eqnarray*} 2n \end{eqnarray*}$ addiert und die Kehrwerte der geraden Zahlen im gleichen Bereich abgezogen.

Stattdessen kann man aber auch alle Kehrwerte(gerade und ungerade) zunächst addieren. Dann wurden aber die geradaden Kehrwerte nicht abgezogen sondern stattdessen nochmal auf die ungeraden aufaddiert. Zieht man also noch 2 mal die geraden Kehrwerte ab, steht auf beiden seiten das gleiche.

In der zweiten Gleichung steht links die Summe der Kehrwerte von Zahlen zwischen $\begin{eqnarray*} n+1 \end{eqnarray*}$ und $\begin{eqnarray*} 2n \end{eqnarray*}$ . Stattdessen kann man aber auch die Kehrwerte aller Zahlen zwischen $\begin{eqnarray*} 1 \end{eqnarray*}$ und $\begin{eqnarray*} 2n \end{eqnarray*}$ addieren und nachher jene, die zuviel sind (nämlich die zwischen $\begin{eqnarray*} 1 \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ ) wieder abziehen.

Ich hoffe dadurch wurde es klarer smile

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen