Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Vollständige Induktion

Vollständige Induktion

Universität / Fachhochschule

Tags: Vollständig Induktion

Elber123 aktiv_icon

04:23 Uhr, 11.12.2011

Hallo zusammen,

Beweise:

1 + 2 + 3 + ... + (n - 1) + n = \frac{n . (n + 1)}{2}

Am Ende bekomme ich diese Gleichung:

\frac{n^{2} + 3 n + 2}{2} = \frac{n^{2} + 5 n + 2}{2}

Was mache ich denn hier falsch???

Gruß
Elber

Chokess aktiv_icon

04:53 Uhr, 11.12.2011

www.onlinemathe.de/forum/Vollstaendige-Induktion-1061

Elber woher sollen die leute wissen, was du falsch gemacht hast, wenn du ihnen nur das Falsche zeigst?

Ich habe von dir bisher noch keine einzige Rechnung oder sonstiges gesehen und ich schreibe mir einen Wolf... Vielleicht solltest du mal deine Motivation hinterfragen und ehrlich mit deinem eigenen Wissen umgehen, sonst wirst du nicht weit in der Mathematik kommen.

Also hör auf nach Lösungen zu fragen, sondern fange an Verständnisfragen zu stellen!

Nach IV gilt:

{(2 (n + 1) - 1)}^{2} + \sum_{i = 1}^{n} {(2 i - 1)}^{2} = {(2 (n + 1) - 1)}^{2} + n \cdot \frac{4 n^{2} - 1}{3}

= {(2 n + 1)}^{2} + \frac{4 n^{3} - n}{3} = 4 n^{2} + 4 n + 1 + \frac{4 n^{3} - n}{3} = \frac{12 n^{2} + 12 n + 3 + 4 n^{3} - n}{3}

= \frac{4 n^{3} + 12 n^{2} + 12 n + 3 \pm n}{3} = \frac{4 n^{3} + 4 n^{2} + 8 n^{2} + 8 n + 4 n + 3 - n}{3}

= \frac{4 n^{3} + 4 n^{2} + 8 n^{2} + 8 n + 3 n + 3}{3} = \frac{4 n^{2} \cdot (n + 1) + 8 n \cdot (n + 1) + 3 \cdot (n + 1)}{3} = (n + 1) \cdot \frac{4 n^{2} + 8 n + 3}{3}

= (n + 1) \cdot \frac{4 n^{2} + 8 n + 4 - 1}{3} = (n + 1) \cdot \frac{4 \cdot (n^{2} + 2 n + 1) - 1}{3} = (n + 1) \cdot \frac{4 {(n + 1)}^{2} - 1}{3}

Wie bin ich auf die einzelnen Schritte gekommen?

MfG Chris

Elber123 aktiv_icon

02:04 Uhr, 12.12.2011

Sorry, aber das ist doch nicht die Aufgabe?!

Elber123 aktiv_icon

02:46 Uhr, 12.12.2011

1 + 2 + 3 + ... + (n - 1) + n = \frac{n \cdot (n + 1)}{2}

\sum_{k = 1}^{n} (k - 1) + k = \frac{n \cdot (n + 1)}{2}

(IA):

n = 1

\sum_{k = 1}^{1} (k - 1) + k = \frac{n \cdot (n + 1)}{2}

(1 - 1) + 1 = \frac{1 \cdot (1 + 1)}{2}

1 = 1

(IS):

n \to n + 1

Ich rechne zunächst die rechte Seite runter:

\sum_{k = 1}^{n + 1} 1 + 2 + 3 + ... + (n + 1) + n + ((n + 1) - 1) + n + 1 = \frac{(n + 1) ((n + 1) + 1)}{2}

\sum_{k = 1}^{n + 1} \frac{n \cdot (n + 1)}{2} + 2 n + 1 = \frac{(n + 1) \cdot (n + 2)}{2}

\sum_{k = 1}^{n + 1} \frac{n \cdot (n + 1)}{2} + 2 n + 1 = \frac{n^{2} + 2 n + n + 2}{2}

\sum_{k = 1}^{n + 1} \frac{n \cdot (n + 1)}{2} + 2 n + 1 = \frac{n^{2} + 3 n + 2}{2}

So, jetzt rechne ich die linke Seite runter, wenn beide Seiten gleich sind, dann sind wir fertig.

\frac{n \cdot (n + 1)}{2} + 2 n + 1 = \frac{n^{2} + n + 2 (2 n + 1)}{2} = \frac{n^{2} + n + 4 n + 2}{2} = \frac{n^{2} + 5 n + 2}{2}

Also:

\frac{n^{2} + 3 n + 2}{2} \neq \frac{n^{2} + 5 n + 2}{2}

Was mache ich denn hier falsch???

Gruß
Elber

PS.: Ich glaube, ich habe den Fehler gefunden.
Also hier setze ich auf der linken Seite "n+1" nur in "n" ein, dann steht gleichung richtig.

\sum_{k = 1}^{n + 1} 1 + 2 + 3 + ... + (n - 1) + n = \frac{n \cdot (n + 1)}{2}

\sum_{k = 1}^{n + 1} 1 + 2 + 3 + ... + (n - 1) + n + 1 = \frac{(n + 1) ((n + 1) + 1)}{2}

\frac{n^{2} + 3 n + 2}{2} = \frac{n^{2} + 3 n + 2}{2}

Chokess aktiv_icon

18:26 Uhr, 12.12.2011

Es ergibt überhaupt keinen Sinn, was du da tust.

Wo ist deine Induktionsvorraussetzung (IV)????

Du kannst nicht einfach etwas hinzudichten!

"So, jetzt rechne ich die linke Seite runter, wenn beide Seiten gleich sind, dann sind wir fertig."

Wie rechnest du die linke Seite runter????? (ergibt keinen Sinn)

Im übrigen ist deine Reihe/Summe falsch! (direkt die zweite Zeile)

Chokess aktiv_icon

10:15 Uhr, 13.12.2011

Ich weiß, dass das nicht die Aufgabe war, aber diese ist um Meilen einfacher als die erste, wenn du die erste verstanden hättest, die einzelnen Schritte, wäre dieser Thread gar nicht erst zu stande gekommen!

Behauptung:

1 + 2 + 3 + ... + (n - 1) + n = \frac{n \cdot (n + 1)}{2}

Dieser Beweis kommt ohne vollständige Induktion aus:

Betrachte

n

gerade und ungerade.

Zunächst

n

gerade:

1 + 2 + 3 + ... + (n - 1) + n = 1 + 2 + 3 + 4 + ... + (n - 4) + (n - 3) + (n - 2) + (n - 1) + n

= [1 + n] + [2 + (n - 1)] + [3 + (n - 2)] + [4 + (n - 3)] + [5 + (n - 4)] + . .

= [n + 1] + [n + 1] + [n + 1] + [n + 1] + . .

.

Da ich von n-gerade Gliedern, jeweils das letzte und erste kombinieren kann, habe ich noch

\frac{n}{2}

-Glieder in der Form

(n + 1)

\Leftrightarrow 1 + 2 + 3 + ... + (n - 1) + n = \frac{n}{2} \cdot (n + 1)

Für n-ungerade Gliedern, sieht es fast genauso aus, nur dass ich nun anders kombiniere:

[1 + (n - 1)] + [2 + (n - 2)] + ... + [k + (n - k)] + n \Leftrightarrow \frac{(n - 1) \cdot n}{2} + n = \frac{(n - 1) \cdot n}{2} + \frac{2 n}{2} = \frac{n \cdot (n - 1 + 2)}{2} = \frac{n \cdot (n + 1)}{2}

q . e . d

.

Vollständige Induktion.

Behauptung:

1 + 2 + 3 + ... + (n - 1) + n = \frac{n \cdot (n + 1)}{2}

Forme erst einmal die linke Seite in eine Reihe um.

Also betrachte

1 + 2 + 3 + ... + (n - 2) + (n - 1) + n

Sei das erste Glied

k,

dann gilt

k = 1 :

k + (k + 1) + (k + 2) + ... + (n - 1 - k) + (n - k) + n

Offensichtlich geht die Summe von

k = 1

bis

n,

also

\sum_{k = 1}^{n}

In einer Summe wird

k

immer um eins erhöht,

k = 1,2,3,4, ... ., n - 2, n - 1, n

.

Und jenes ist gerade die Folge die wir suchen.

\Rightarrow \sum_{k = 1}^{n} k

Insbesondere gilt also:

1 + 2 + 3 + ... + (n - 1) + n = \sum_{k = 1}^{n} k

Wir können nun unsere linke Seite von der Ausgangs-Behauptung ersetzen und es bleibt zu zeigen:

\sum_{k = 1}^{n} k = \frac{n \cdot (n + 1)}{2}

Lösungsansatz:
Wenn wir ein beliebiges

n

finden für das unsere Behauptung erfüllt ist, und dann zeigen können, dass jedes darauffolgende

n

die Gleichung erfüllt, so erfüllt auch jedes vorhergehende

n

die Gleichung und umgekehrt. Und somit würde jedes

n

die Gleichung erfüllen.

\Leftrightarrow

Nun können wir die vollständige Induktion als Beweisform ansetzen.

Wir betrachten ausschließlich die linke Seite und wollen zeigen, dass diese genau die rechte Seite ergibt.

Zu erst prüfen wir, ob unsere Gleichung überhaupt für irgend ein

n

gilt. Induktionsanfang (IA)
Sei also

n = 1,

dann ist

\sum_{k = 1}^{1} k = 1 = \frac{2}{2} = \frac{1 \cdot (1 + 1)}{2},

also erfüllt.

Wobei wir mit dem IA gezeigt haben, dass für unser

n

die Gleichung

\sum_{k = 1}^{n} k = \frac{n \cdot (n + 1)}{2}

erfüllt ist. Also ist

\sum_{k = 1}^{n} k = \frac{n \cdot (n + 1)}{2}

die Induktionsvorraussetzung (IV).

Es bleibt entweder

n \to n + 1

oder

n \to n - 1

zu betrachten.

Denn wenn

1 \to 2

gilt, dann auch

2 \to 3

und so weiter.
Wenn

1 \to 0

gilt, dann auch

2 \to 1, 3 \to 2

und so weiter.

Ich wähle für meinen Induktionsschritt (IS)

n \to n + 1,

dann passiert folgendes:

\sum_{k = 1}^{n} k = \frac{n \cdot (n + 1)}{2} \to \sum_{k = 1}^{n + 1} k = \frac{(n + 1) \cdot ((n + 1) + 1)}{2}

Wobei die linke Seite vom Pfeil unser IV ist und für

n = 1

gilt. Wir zeigen nun, dass daraus die rechte Seite des Pfeils folgt.

Also betrachte die linke Seite von

\sum_{k = 1}^{n + 1} k = \frac{(n + 1) \cdot ((n + 1) + 1)}{2}

und zeige, dass mit Hilfe der IV, die linke genau die rechte Seite ist.

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

Nun ist nach IV

\sum_{k = 1}^{n} k = \frac{n \cdot (n + 1)}{2}

und es folgt:

\sum_{k = 1}^{n} k + (n + 1) = \frac{n \cdot (n + 1)}{2} + (n + 1) = (n + 1) (\frac{n}{2} + 1) = (n + 1) \frac{n + 2}{2} = (n + 1) \frac{(n + 1) + 1}{2}

Also ist gezeigt, dass

\sum_{k = 1}^{n} k = \frac{n \cdot (n + 1)}{2} \to \sum_{k = 1}^{n + 1} k = \frac{(n + 1) \cdot ((n + 1) + 1)}{2}

gilt.

\Rightarrow

die Ursprungsbehauptung.

Es gilt

1 + 2 + 3 + ... + (n - 1) + n = \frac{n \cdot (n + 1)}{2}

q . e . d

.

Ohne Erklärungen sieht das ganz natürlich viel kürzer aus, ich zeige es mal für

n \to n - 1

.

IA

(n = 1) : \sum_{k = 1}^{1} k = 1 = \frac{2}{2} = \frac{1 \cdot (1 + 1)}{2}

(n \to n - 1) : \sum_{k = 1}^{n - 1} k = (\sum_{k = 1}^{n} k) - n

nach IV:

= \frac{n \cdot (n + 1)}{2} - n = \frac{(n \cdot (n + 1)) - 2 n}{2} = \frac{n \cdot (n + 1 - 2)}{2} = \frac{n \cdot (n - 1)}{2} = \frac{((n - 1) + 1) \cdot (n - 1)}{2}

q . e . d

.

MfG Chris

Elber123 aktiv_icon

04:08 Uhr, 15.12.2011

Vielen Dank für die ausführliche Erklärung!

Ich könnte dennoch ab hier die Aufgabe so lösen:

(IV):

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

(IA):

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

\sum_{k = 1}^{1} k = \frac{1 (1 + 1)}{2}

1 = 1

(IS):n

\to n + 1

\sum_{k = 1}^{n + 1} k = \frac{(n + 1) ((n + 1) + 1)}{2} = \frac{(n + 1) (n + 2)}{2} = \frac{n^{2} + 3 n + 2}{2}

So, und jetzt müssen wir zeigen, dass

\sum_{k = 1}^{n + 1} k = \frac{n^{2} + 3 n + 2}{2}

ist.

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

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

\sum_{k = 1}^{n + 1} k = \frac{n^{2} + n + 2 n + 2}{2}

\sum_{k = 1}^{n + 1} k = \frac{n^{2} + 3 n + 2}{2}

q . e . d

.

lg
Elber

Chokess aktiv_icon

05:59 Uhr, 15.12.2011

Natürlich könnte man beide Seiten einfach ausmultiplizieren.

Aber man möchte in der Mathematik halt gerne zeigen, dass das Eine, das Andere ist und nicht, dass wenn ich beide verändere sie sich in der Mitte treffen.

Das ist aber nur Formsache, denn du kannst dein Ausmultipliziertes schließlich auch in Rückrichtung betrachten.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

952667

950621

	Status: nicht eingeloggt	Noch nicht registriert?