Vollständige Induktion

03.01.2006, 21:16

marci_

Vollständige Induktion

ja, also mir ist da schon irgendwie klar, auf was man hinauswill..
nur versteh ich die vorgehensweise nicht so..
gibts da irgendwie ein schema?

03.01.2006, 21:19

MrPSI

Auf diesen Beitrag antworten »

zuerst nimmt man an, dass das Gegebene für ein beliebiges n gilt, und beweist, dass es auch für (n+1) gilt, das nennt man Induktionsschluss.
Und wenn man jetzt den Induktionsanfang macht, also das Gegebenen für den Fall n=1 beweist, dann kann man mit der vorhin gewonnenen Erkenntnis(=es gilt auch für den nächsten Fall, und dann wieder für den nächsten....) das Gegebene auf die gesamte Menge der natürlichen Zahlen ausweiten.
Alles klar?

03.01.2006, 21:30

marci_

Auf diesen Beitrag antworten »

wenn es heißt:
An: 2+4+6+...+2n=n*(n+1)
für n=1
n=2
n=3 stimmt es
muss ich dann einfach (n+1) auf jeder seite dazuaddieren`?

A(n+1) 2+4+6+...2n+2(n+1)=(n+1)*((n+1)+1)
An +2n+2 = (n+1)*(n+2)
An+2n+2 =n²+2n+n+2
An =n²+n

und das steht ja in der ersten zeile
geht das dann so?

03.01.2006, 21:46

freetgy

Auf diesen Beitrag antworten »

1. Induktionsvorraussetzung:
(Du beweist für ein kleinst mögliches $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$
das eine Reihe gilt.
z.b.
Beweise das hier:
$\begin{eqnarray*} A(n) = \sum_{i=1}^n~(2i-1) = n^2 \end{eqnarray*}$

jetzt testest du ob dies für ein möglichst kleines n gilt:

Annahme für n=1 ist diese Aussage wahr:
$\begin{eqnarray*} \sum_{i=1}^1~(2i-1) = n^2 \end{eqnarray*}$ .
$\begin{eqnarray*} = (2*1-1) = 1^2 \end{eqnarray*}$ .
$\begin{eqnarray*} 1 = 1 \end{eqnarray*}$

Dadurch haste gezeigt die obige Aussage gilft für n = 1.

2.
Induktionsvorrausetzung:
Da du in 1. gezeigt hast das es für ein mögliches n gilt.
sagst du es sei für alle A(n) (ab n = Induktionsanfang (hier 1) wahr
$\begin{eqnarray*} A(n) = \sum_{i=1}^n~(2i-1) = n^2 \end{eqnarray*}$

3.
Induktionsbehauptung:
Da obiges als wahr angenommen wird (was nicht sein muss!)
müsste dann aber auch gelten A(n+1) muss dann auch wahr sein:
$\begin{eqnarray*} A(n+1) = \sum_{i=1}^{n+1}~(2i-1) = (n+1)^2 \end{eqnarray*}$

4.
Induktionsschluss:
(Der eigentliche Beweis!!)
Jetzt musst du unter verwendung von 2.
aus $\begin{eqnarray*} \sum_{i=1}^{n+1}~(2i-1) \end{eqnarray*}$ das herleiten: $\begin{eqnarray*} (n+1)^2 \end{eqnarray*}$

----
Beweisschritt:
$\begin{eqnarray*} \sum_{i=1}^{n+1}~(2i-1) = (n+1)^2 \end{eqnarray*}$
die Summe kannst du auch abspalten udn schreiben als
$\begin{eqnarray*} \sum_{i=1}^n~(2i-1)+ (2*(n+1)-1) = (n+1)^2 \end{eqnarray*}$
da darin jetzt wieder das auftaucht (verwendung von 2.):
$\begin{eqnarray*} \sum_{i=1}^n~(2i-1) \end{eqnarray*}$ kannste es ersetzen mit $\begin{eqnarray*} n^2 \end{eqnarray*}$

daraus folgt:
$\begin{eqnarray*} n^2 + (2*(n+1)-1) = (n+1)^2 \end{eqnarray*}$
jetzt noch ausmultiplizieren ergibt:
$\begin{eqnarray*} n^2 + 2n +2 -1 = (n+1)^2 \end{eqnarray*}$
das ist gleich:
$\begin{eqnarray*} n^2 + 2n + 1 = (n+1)^2 \end{eqnarray*}$
jetzt noch 1. binomische Formel anwenden:
$\begin{eqnarray*} (n+1)^2 = (n+1)^2 \end{eqnarray*}$

--> bewiesen

Was haben wir gemacht?
1.
Wir haben gesagt für n = 1 stimmst:
2.
Wir nehmen an es stimmt für alle n (wissen wir aber nicht, nur angenommen!)
3.
Dann muss es logischer weise (wenn obiges gelte) auch für n+1 gelten.
4.
haben wir n+1 bewiesen.
(Falls 4. nicht klappt wahr wohl die Annahme falsch!)

fängste bei
n=1
n+1 = 1+1 = 2
n+1 = 2+1 = 3 usw...

wodurch wir rekursiv auch A(n) bewiesen hätten.

also gilt diese dieser Zusammenhang für:
$\begin{eqnarray*} A(n) = \sum_{i=1}^n~(2i-1) = n^2 \end{eqnarray*}$
$\begin{eqnarray*} n \geq 1 \end{eqnarray*}$

----------------------------------------------

So einmal ausführlich so hab ichs nämlich auch ein mal gebraucht:

zu sagen bleibt:
1. 2. 3. sind einfach
4. ist das einzig schwierige.

Beweise können unterschiedlich schwierig sein, man brauch meistens nur die richtige idee. (Abspalten , zusammenfassen, oder ähnliches)

03.01.2006, 21:49

marci_

Auf diesen Beitrag antworten »

dankeschön, stimmt dann auch mein beweis?

03.01.2006, 21:51

MrPSI

Auf diesen Beitrag antworten »

Wenn die Formel auch für den nächsten Fall gilt so müsste die Gleichung so wie du es schon gezeigt hast aussehen, also 2+4+6+...+2n+2(n+1)=(n+1)(n+2).
Und das will man jetzt beweisen.
Die Gleichung für den Fall n lautet:
2+4+6+...+2n=n*(n+1)

Jetzt wird die Formel auf (n+1) ausgeweitet, also wird links und rechts
2(n+1) eingefügt. Wenn man dann noch ein wenig umformt, so kommt man auf 2+4+6+...+2n+2(n+1)=(n+1)(n+2) und damit wäre der Induktionsschluss gemacht.

//edit: zu spät

03.01.2006, 21:52

freetgy

Auf diesen Beitrag antworten »

ich schreib es mal anders für dich auf:
$\begin{eqnarray*} \sum_{k=1}^n~ (2k) = n*(n+1) \end{eqnarray*}$

ist das selbe
vielleicht hilft dir das weiter smile

kannst ja analog versuchen

03.01.2006, 21:53

lego

Auf diesen Beitrag antworten »

ja sieht gut aus, du hast das ganze aber anscheinend rückwärts gemacht

03.01.2006, 21:55

marci_

Auf diesen Beitrag antworten »

ja, das hat mir mein lehrer auch schon gesagt, aber kann man das irgendwie so gelten lassen?

03.01.2006, 21:59

freetgy

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
ja, das hat mir mein lehrer auch schon gesagt, aber kann man das irgendwie so gelten lassen?

wenn du das mit der Summe machst sieht das besser aus:
is auch ganz einfach wenn du es analog zu meinem Beispiel machst
(habs ja extra ausführlich gemacht)

mfg

03.01.2006, 22:04

lego

Auf diesen Beitrag antworten »

Zitat:

Original von marci_
ja, das hat mir mein lehrer auch schon gesagt, aber kann man das irgendwie so gelten lassen?

zur not schreibst du es einfach nochmal rückwärts an, dann siehts aus wie normalerweise

aber voricht, wenn du rückwärts rechnest und andere zeichen als das "=" verwendest. denn dann muss nicht zwangsläufig auch gelten, dass das ganze noch richtig ist, wenn man es rückwärts aufschreibt

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen