vollständige induktion

08.11.2007, 16:49

ulibear

vollständige induktion

ich kapier die sache mit dieser vollständigen induktion nicht.

ich scheitere schon an der ersten und wohl einfachsten aufgabe:

"Man beweise durch vollständige induktion für alle n element der natürlichen Zahlen"

a) 1 + 3 + 5 + .... + (2n-1) = n²

so, jetzt steht in der lösung folgendes:

k = 1: 1 = 1²

k -> k + 1: 1 + 3 + 5 + .... + (2k - 1) + (2k + 1) = k² + (2k + 1) = (k+1)²

diese david copperfield aufgaben lieb ich ja, schwubs steht ein elefant auf der bühen, woher bitte kommt den jetz diese (2k + 1) ? woher weis ich das jetzt da jetzt eine (2k + 1) addieren muss?

seltsamer weise neben die in den bücher auch immer das beispiel 1 = 1²....das is ja schön, aber 2 = 2² passt da schon nicht mehr.

ich würd sagen ich raffs das thema vorn und hinten nicht....

08.11.2007, 17:08

20_Cent

Auf diesen Beitrag antworten »

1+3+5+... soll wohl alle ungeraden(!) Zahlen andeuten. 2 ist gerade.
Deswegen addiert man nach 2k-1 auch 2k+1, das ist nämlich genau die nächste ungerade Zahl.
mfG 20

08.11.2007, 17:16

ulibear

Auf diesen Beitrag antworten »

ok....wie kommt man von

k² + (2k + 1) nach (k+1)²

ist das nicht dann 2k³ + k² ?

08.11.2007, 17:45

hxh

Auf diesen Beitrag antworten »

k² + 2k +1 ist die 1. bin formel ausmultipliziert

08.11.2007, 17:55

ulibear

Auf diesen Beitrag antworten »

ahso, ok. danke. sowas hät ich in 20 jahren nicht gesehen.

aber wieso habe ich den mit (n+1)² die induktion bewiesen?......

08.11.2007, 18:18

ulibear

Auf diesen Beitrag antworten »

hab hier noch so eine übungsaufgabe:

$\begin{eqnarray*} a + (a + d) + (a + 2d) + ... + (a + (n - 1)d) = n * a + \frac{n(n-1)}{2}d \end{eqnarray*}$

und wieder eine lösung die ich nicht so richtig verstehe

k = 1: a = 1 * a + 0 *d
k -> k + 1:

a + (a + d) + .... + (a + (k - 1)d) + (a + k * d)

$\begin{eqnarray*} = k *a + \frac{k(k-1)}{2}*d + (a + k * d) \end{eqnarray*}$ Hier is noch verständlich

$\begin{eqnarray*} = (k+1)a + \frac{k(k-1) + 2k}{2} \end{eqnarray*}$ wohin verschwinden den jetzt (a + k *d) ? woher kommt 2k im zähler?

$\begin{eqnarray*} = (k+1)a + \frac{(k + 1)k}{2}*d \end{eqnarray*}$ was in den jetzt passiert? das d is ja wieder da? und 2k weg

ich könnt heulen......

08.11.2007, 19:11

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von ulibear
$\begin{eqnarray*} = k *a + \frac{k(k-1)}{2}*d + (a + k * d) \end{eqnarray*}$ Hier is noch verständlich

$\begin{eqnarray*} = (k+1)a + \frac{k(k-1) + 2k}{2} \end{eqnarray*}$ wohin verschwinden den jetzt (a + k *d) ? woher kommt 2k im zähler?

Vielleicht wird es verständlicher, wenn man mal nur einen Schritt nach dem anderen macht:

$\begin{eqnarray*} k *a + \frac{k(k-1)}{2}*d + (a + k * d) = k *a + a + \frac{k(k-1)}{2}*d + k * d = (k+1) \cdot a + d \cdot \left(\frac{k(k-1)}{2} + k \right) \end{eqnarray*}$

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

Allerdings hast du beim Abschreiben zwischendurch den Faktor d verschlampert.

Was die vollständige Induktion angeht, solltest du dir da nochmal das Prinzip verinnerlichen. Vielleicht hilft
[WS] Vollständige Induktion

08.11.2007, 19:32

ulibear

Auf diesen Beitrag antworten »

hm.....ok.

danke für den wörkshop link...leider is der workshop genau an der stelle ungenau die für mich interessant ist.

im workshop soll ja n-> n+ 1 bewiesen werden.(also das erste beispiel)

woher weis ich den, das der beweis für diesen fall (n² + 3n + 2 )/ 2 sein muss? woran mach ich das fest, is das so offensichtlich das es nicht erwähnt wird?

warum wird
$\begin{eqnarray*} \frac{n(n+1)}{2} \end{eqnarray*}$

dann im ersten schritt so erweitert?

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

wenn du mir die fragen beantworten könntest, hab ich es evtl. verstanden.

08.11.2007, 19:43

klarsoweit

Auf diesen Beitrag antworten »

RE: vollständige induktion
Es geht ja darum, eine Aussage A(n) zu beweisen, die eben für alle natürlichen Zahlen n gelten soll. In dem Beispiel im Workshop lautet die:

$\begin{eqnarray*} 1 + 2 + ... + n = \frac{n(n+1)}{2} \end{eqnarray*}$

Oder, wenn du das Summenzeichen kennst:

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

Bei der vollständigen Induktion macht man beim Induktionsschritt folgendes:
Man nimmt an, daß die Aussage A für ein bestimmtes n wahr ist, das heißt, man nimmt an, daß A(n) wahr ist. Dann zeigt man, daß die Aussage A auch für den Nachfolger von n, also für n+1, wahr. Man muß also die Gültigkeit der Aussage A(n+1) zeigen, wobei - wie gesagt - man verwenden darf, daß A(n) wahr ist.

Was gerne nicht gemacht wird, ich aber immer empfehle, ist, die Aussage A(n+1) mal hinzuschreiben. Dazu ersetzt man jedes n durch n+1:

$\begin{eqnarray*} 1 + 2 + ... + n + n+1 = \frac{(n+1)(n+1+1)}{2} \end{eqnarray*}$

Jetzt nimmt man sich davon die linke Seite und formt die solange um, bis man die rechte Seite erhält. Das war's.

Nicht vergessen darf man den Induktionsanfang. Man muß ja schließlich zeigen, daß es tatsächlich einen konkreten Wert für n gibt, wo die Aussage A wahr ist.

08.11.2007, 19:54

ulibear

Auf diesen Beitrag antworten »

danke,

die grobe logik dahinter hab ich verstanden, das doing aber noch nicht ganz

wieso wird aus

$\begin{eqnarray*} ....= \frac{n(n+1)}{2} \end{eqnarray*}$

$\begin{eqnarray*} .... = \frac{(n+1)(n+1+1)}{2} \end{eqnarray*}$

Das müsste doch so sein:
$\begin{eqnarray*} .... = \frac{n(n+1)+ (n+1)}{2} \end{eqnarray*}$

da ich ja mit +(n+1) erweitere?

08.11.2007, 22:09

klarsoweit

Auf diesen Beitrag antworten »

Nein. Hier wird nichts erweitert. Hier wurde das gemacht:

Zitat:

Original von klarsoweit
Was gerne nicht gemacht wird, ich aber immer empfehle, ist, die Aussage A(n+1) mal hinzuschreiben. Dazu ersetzt man jedes n durch n+1:

$\begin{eqnarray*} 1 + 2 + ... + n + n+1 = \frac{(n+1)(n+1+1)}{2} \end{eqnarray*}$

09.11.2007, 18:17

ulibear

Auf diesen Beitrag antworten »

Eine hoffentlich letzte Frage hab ich dann noch

woher weis ich den, das der beweis für diesen fall (n² + 3n + 2 )/ 2 sein muss? woran mach ich das fest, is das so offensichtlich das es nicht erwähnt wird?

09.11.2007, 18:33

Auf diesen Beitrag antworten »

Es sollte reichen, einfach die Klammern aufzulösen. Es ist:
$\begin{eqnarray*} \frac{(n+1)(n+1+1)}{2}=\frac{(n+1)(n+2)}{2}=\frac{(n^2+n+2n+2)}{2}=\frac{(n^2+3n+2)}{2} \end{eqnarray*}$
Da du das erste beweisen musst, hast du es bewiesen, wenn du auf das Vierte kommst Augenzwinkern

.

Gruß
MI

09.11.2007, 18:53

ulibear

Auf diesen Beitrag antworten »

Zitat:

Original von MI
Es sollte reichen, einfach die Klammern aufzulösen. Es ist:
$\begin{eqnarray*} \frac{(n+1)(n+1+1)}{2}=\frac{(n+1)(n+2)}{2}=\frac{(n^2+n+2n+2)}{2}=\frac{(n^2+3n+2)}{2} \end{eqnarray*}$
Da du das erste beweisen musst, hast du es bewiesen, wenn du auf das Vierte kommst Augenzwinkern

.

Gruß
MI

kann ich also nicht vorher wissen?

kann ich meinen beweis irgendwie gegenprüfen? ich kann ihn zwar ausrechnen, aber ich verstehe ehrlich gesagt nicht was ich da bewiesen hab. kann man da dann wieder die zahl 1 für die unbekannt einsetzen und es muss 1 rauskommen?

09.11.2007, 23:23

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von ulibear
kann ich also nicht vorher wissen?

Was willst du vorher wissen, vor allem vor was?

Villeicht solltest du dir das Prinzip nochmal klarmachen:

Du hast bei der vollständigen Induktion für die Aussage A zwei Dinge gezeigt:

1. A(1) ist wahr
2. Wenn A(n) wahr ist, dann ist auch A(n+1) wahr.

Jetzt brauchst du in den 2. Punkt nur nacheinander alle natürlichen Zahlen einsetzen:
Wenn A(1) wahr ist (das wissen wir wegen 1.), dann ist auch A(2) wahr.
Wenn A(2) wahr ist, dann ist auch A(3) wahr. Usw.

Dieser Zusammenhang wird gerne auch mit dem Dominoeffekt verglichen.

Neue Frage »

Antworten »

vollständige induktion

Verwandte Themen