der kleine Gauß < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:10 Sa 12.04.2008 | | Autor: | dau2 |
Hi,
habe hier einen Induktionsbeweis der gar nichts für mich aussagt, vielleicht habt ihr eine idee wie man die begründung warum es funktioniert erklären kann:
Soll bewiesen werden:
1+2+...+n = [mm] \bruch{1}{2}n(n+1)
[/mm]
Induktionsanfang
[mm] 1=\bruch{1}{2}*1(1+1)
[/mm]
Induktionsschluss
1+2+...+k+(k+1) = [mm] \bruch{1}{2}k(k+1)+(k+1) [/mm] = [mm] \bruch{1}{2}(k+1)(k+2) [/mm] = [mm] \bruch{1}{2}(k+1)((k+1)+1)
[/mm]
Damit ist:
1+2+...k+(k+1) = [mm] \bruch{1}{2}(k+1)((k+1)+1)
[/mm]
gezeigt, was genau A(k+1) entspricht
Die Umformungen kann ich nachvollziehen, aber am Ende sehe ich nicht wie damit etwas bewiesen wurden ist....es wurde ja nur "anders hingeschrieben"?
Mfg
dau2
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:12 Sa 12.04.2008 | | Autor: | MacMath |
Sehe ich das richtig das es hier allgemein um das Verständnis des Induktionsprinzips geht?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:14 Sa 12.04.2008 | | Autor: | dau2 |
Ich hoffe es.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:29 Sa 12.04.2008 | | Autor: | MacMath |
OK, beliebt ist der Anschauliche Vergleich mit einer Dominokette.
Verfolgen wir diesen Ansatz, zumindest nutze ich ihn als begleitende Stütze.
Auf die Rechtfertigung der Induktion mit den Peano-Axiomen können wir jetzt denke ich verzichten, da diese sehr trockene Ansicht das Verständnis wohn nicht fördert.
Wir betrachten unsere Aussage [mm] A_n, [/mm] und wollen zeigen: [mm] A_n [/mm] ist wahr für alle [mm] n\in\IN [/mm]
(Unsere Dominokette besteht aus den einzelnen "Steinen" [mm] A_n, [/mm] bewiesen ist, wer umfällt ;) Nun stoßen wir die Kette an:)
Induktionsanfang:
[mm] A_1 [/mm] ist wahr. Diese Aussage zeigst du durch direktes Nachrechnen.
Wir zeigen hier es gibt wenigstens eine natürliche Zahl für welche die Aussage stimmt.
Induktionsvoraussetzung: (*)
Sei [mm] n\in\IN [/mm] beliebig aber fest gewählt sodass [mm] A_n [/mm] bewiesen ist
---
Schnipp...Warum darf ich das sagen wenn [mm] A_n [/mm] nicht bewiesen ist?
Nun ja, ich muss mein n eben so "wählen" DASS die Aussage schon bewiesen wurde für dieses n. Der Induktionsanfang garantiert mir das ich immer ein solches n wählen kann, im Notfall 1 :)
---
Induktionsschritt:
Hier wissen wir nach der Induktionsvoraussetzung dass [mm] A_n [/mm] für das "aktuelle" n korrekt ist. Daraus folgern wir die Aussage [mm] A_{n+1}
[/mm]
In deinem Beispiel zB ist hier zu zeigen dass KleinGauss(n+1) = KleinGauss(n)+ n+1
[Die Abkürzung musste sein sry]
Gelingt uns dies, haben wir die Menge der [mm] n\in\IN [/mm] für die [mm] A_n [/mm] stimmt um (n+1) ergänzt. Also dürften wir in (*) auch diese Zahl für n wählen, woraus wieder die nächste Zahl folgt usw....
Wir haben eine Endlosschleife gestartet die unseren Beweis auf ganz [mm] \IN [/mm] überträgt.
Ich hoffe das war einigermaßen nachvollziehbar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:09 So 13.04.2008 | | Autor: | dau2 |
> OK, beliebt ist der Anschauliche Vergleich mit einer
> Dominokette.
> Verfolgen wir diesen Ansatz, zumindest nutze ich ihn als
> begleitende Stütze.
> Auf die Rechtfertigung der Induktion mit den Peano-Axiomen
> können wir jetzt denke ich verzichten, da diese sehr
> trockene Ansicht das Verständnis wohn nicht fördert.
Sehr gute Entscheidung :)
>
> Wir betrachten unsere Aussage [mm]A_n,[/mm] und wollen zeigen: [mm]A_n[/mm]
> ist wahr für alle [mm]n\in\IN[/mm]
> (Unsere Dominokette besteht aus den einzelnen "Steinen"
> [mm]A_n,[/mm] bewiesen ist, wer umfällt ;) Nun stoßen wir die Kette
> an:)
>
> Induktionsanfang:
> [mm]A_1[/mm] ist wahr. Diese Aussage zeigst du durch direktes
> Nachrechnen.
> Wir zeigen hier es gibt wenigstens eine natürliche Zahl
> für welche die Aussage stimmt.
>
> Induktionsvoraussetzung: (*)
> Sei [mm]n\in\IN[/mm] beliebig aber fest gewählt sodass [mm]A_n[/mm] bewiesen
> ist
> ---
> Schnipp...Warum darf ich das sagen wenn [mm]A_n[/mm] nicht bewiesen
> ist?
Wird [mm]A_n[/mm] (wobei n eine gewählte Zahl ist) nicht durch den Induktionsanfang zwangsläufig bewiesen?
> Nun ja, ich muss mein n eben so "wählen" DASS die Aussage
> schon bewiesen wurde für dieses n. Der Induktionsanfang
> garantiert mir das ich immer ein solches n wählen kann, im
> Notfall 1 :)
> ---
>
> Induktionsschritt:
> Hier wissen wir nach der Induktionsvoraussetzung dass [mm]A_n[/mm]
> für das "aktuelle" n korrekt ist. Daraus folgern wir die
> Aussage [mm]A_{n+1}[/mm]
> In deinem Beispiel zB ist hier zu zeigen dass
> KleinGauss(n+1) = KleinGauss(n)+ n+1
> [Die Abkürzung musste sein sry]
>
> Gelingt uns dies, haben wir die Menge der [mm]n\in\IN[/mm] für die
> [mm]A_n[/mm] stimmt um (n+1) ergänzt. Also dürften wir in (*) auch
> diese Zahl für n wählen, woraus wieder die nächste Zahl
> folgt usw....
> Wir haben eine Endlosschleife gestartet die unseren Beweis
> auf ganz [mm]\IN[/mm] überträgt.
>
> Ich hoffe das war einigermaßen nachvollziehbar
Wäre es dann nicht besser am Ende zum Beweis des ganzen sowas wie
1 = 1 stehen zu haben, also etwas was auch optisch auf den ersten Blick gleich ist?
Sonst könnte ich ja bei jeder Induktion einfach n+1 anhängen noch ein wenig umformen zur Verwirrung und sagen das passt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:57 So 13.04.2008 | | Autor: | Marcel |
Hallo,
> > OK, beliebt ist der Anschauliche Vergleich mit einer
> > Dominokette.
> > Verfolgen wir diesen Ansatz, zumindest nutze ich ihn als
> > begleitende Stütze.
> > Auf die Rechtfertigung der Induktion mit den
> Peano-Axiomen
> > können wir jetzt denke ich verzichten, da diese sehr
> > trockene Ansicht das Verständnis wohn nicht fördert.
>
> Sehr gute Entscheidung :)
>
> >
> > Wir betrachten unsere Aussage [mm]A_n,[/mm] und wollen zeigen: [mm]A_n[/mm]
> > ist wahr für alle [mm]n\in\IN[/mm]
> > (Unsere Dominokette besteht aus den einzelnen "Steinen"
> > [mm]A_n,[/mm] bewiesen ist, wer umfällt ;) Nun stoßen wir die Kette
> > an:)
> >
> > Induktionsanfang:
> > [mm]A_1[/mm] ist wahr. Diese Aussage zeigst du durch direktes
> > Nachrechnen.
> > Wir zeigen hier es gibt wenigstens eine natürliche Zahl
> > für welche die Aussage stimmt.
> >
> > Induktionsvoraussetzung: (*)
> > Sei [mm]n\in\IN[/mm] beliebig aber fest gewählt sodass [mm]A_n[/mm]
> bewiesen
> > ist
> > ---
> > Schnipp...Warum darf ich das sagen wenn [mm]A_n[/mm] nicht
> bewiesen
> > ist?
>
> Wird [mm]A_n[/mm] (wobei n eine gewählte Zahl ist) nicht durch den
> Induktionsanfang zwangsläufig bewiesen?
>
>
> > Nun ja, ich muss mein n eben so "wählen" DASS die Aussage
> > schon bewiesen wurde für dieses n. Der Induktionsanfang
> > garantiert mir das ich immer ein solches n wählen kann, im
> > Notfall 1 :)
> > ---
> >
> > Induktionsschritt:
> > Hier wissen wir nach der Induktionsvoraussetzung dass [mm]A_n[/mm]
> > für das "aktuelle" n korrekt ist. Daraus folgern wir die
> > Aussage [mm]A_{n+1}[/mm]
> > In deinem Beispiel zB ist hier zu zeigen dass
> > KleinGauss(n+1) = KleinGauss(n)+ n+1
> > [Die Abkürzung musste sein sry]
> >
> > Gelingt uns dies, haben wir die Menge der [mm]n\in\IN[/mm] für die
> > [mm]A_n[/mm] stimmt um (n+1) ergänzt. Also dürften wir in (*) auch
> > diese Zahl für n wählen, woraus wieder die nächste Zahl
> > folgt usw....
> > Wir haben eine Endlosschleife gestartet die unseren
> Beweis
> > auf ganz [mm]\IN[/mm] überträgt.
> >
> > Ich hoffe das war einigermaßen nachvollziehbar
>
>
> Wäre es dann nicht besser am Ende zum Beweis des ganzen
> sowas wie
> 1 = 1 stehen zu haben, also etwas was auch optisch auf den
> ersten Blick gleich ist?
wenn man - unter Verwendung der Induktionsvoraussetung - nur äquivalente Umformungen macht, wird das wohl gehen (weil man dann ja sogar zeigt: $A(n) [mm] \mbox{ ist wahr} \gdw [/mm] A(n+1) [mm] \mbox{ ist wahr}$). [/mm] Aber Du hast ja zwei Dinge zu zeigen:
1.) Die Aussage $A(1)$ ist korrekt.
2.) Wenn es ein $n [mm] \in \IN$ [/mm] gibt, so dass $A(n)$ stimmt, dann stimmt auch $A(n+1)$.
(D.h.: $A(n) [mm] \mbox{ ist wahr } \Rightarrow [/mm] A(n+1) [mm] \mbox{ ist wahr}$, [/mm] und das ist "weniger" wie oben mit dem [mm] $\gdw$, [/mm] weil: Wenn man $A [mm] \gdw [/mm] B$ zeigt, zeigt man: $A [mm] \Rightarrow [/mm] B [mm] \mbox{ \underline{und} }B \Rightarrow [/mm] A$. Die Richtung $A(n+1) [mm] \mbox{ wahr } \Rightarrow [/mm] A(n) [mm] \mbox{ wahr}$ [/mm] steht aber beim Induktionsbeweis gar nicht mit drin.)
Was ist die Konsequenz von dem gezeigten?
Weil $A(1)$ gilt, gilt dann auch $A(2)$.
Weil nun $A(2)$ gilt, gilt wiederum $A(3)$.
Weil $A(3)$ gilt, gilt wiederum $A(4)$...
Stelle es Dir so vor:
Du hast Dominosteine so aufgestellt, dass auf dem $n$-ten Dominostein (er trage die Nummer $n$) die Aussage $A(n)$ steht. Wenn der Beweis des Induktionsschrittes $n [mm] \mapsto [/mm] n+1$ klappt, so bedeutet das für die Dominosteine, das sie so nahe beieinander stehen, dass, wenn Du den $k$-ten Dominostein umwirfst, dann alle hinter $k$-stehenden Dominosteine umfallen (beachte, dass wir uns vorzustellen haben, dass wir soviel Dominosteine haben, wie [mm] $\IN$ [/mm] Elemente hat). Wenn der Beweis des Induktionsschrittes nicht klappt, so bedeutet dies hier, dass wir nicht wissen, ob die Dominosteine "in diesem Sinne nahe genug beieinander" stehen.
Ein gefallener Dominostein bedeutet, wenn er die Nummer [mm] $k_0$ [/mm] hat, dass [mm] $A(k_0)$ [/mm] auf jeden Fall stimmt. (Für einen Dominostein, der stehenbleibt, treffen wir i.a. keine Aussage über den Wahrheitswert der zugehörigen Aussage).
Was ist die Konsequenz? Wenn wir einen Induktionsbeweis führen und der Induktionsschritt $n [mm] \mapsto [/mm] n+1$ klappt, bedeutet das für die Dominosteine, dass sie jedenfalls so nahe beieinander stehen, dass, wenn einer umfällt, alle darauffolgenden auch umfallen (Konsequenz: Ab dem umgefallen Dominostein mit der Nummer [mm] $n_0$ [/mm] sind auch alle darauffolgenden Aussagen wahr, d.h. $A(n)$ ist dann gültig für alle $n [mm] \ge n_0$). [/mm] Damit wir die Steine aber überhaupt fallen sehen können (wir wissen ja nur über die gefallenen Steine, dass die zugehörigen Aussagen stimmen), müssen wir einen ersten umschmeißen. Wenn wir [mm] $n_0=1$ [/mm] wählen können, sehen wir, weil dann ein jeder Stein einmal umfallen wird, dass die Aussage $A(n)$ für jedes $n [mm] \ge [/mm] 1$ gilt. Wenn wir den Induktionsstart mit [mm] $n_0=7$ [/mm] machen, also erst den siebten Stein wählen, um ihn umzuschmeißen und er fällt (d.h. Beweis: $A(7)$ stimmt), dann wissen wir, weil $A(7)$ fällt und die Steine nahe genug beieinander stehen (das zeigt der Beweis des Induktionsschrittes $n [mm] \mapsto [/mm] n+1$, wenn er uns denn gelingt), wird jeder Stein mit einer Nummer $n [mm] \ge [/mm] 7$ irgendwann mal fallen, also $A(n)$ stimmt dann für jedes $n [mm] \ge [/mm] 7$. Wie das mit den Steinen mit den Nummern $1,...,6$ dann ist, muss man dann separat nachprüfen.
> Sonst könnte ich ja bei jeder Induktion einfach n+1
> anhängen noch ein wenig umformen zur Verwirrung und sagen
> das passt.
Nein, in dem Induktionsschritt geht ja explizit der Wahrheitsgehalt der Aussage $A(n)$ ein, wenn man zeigen will, dass dann auch $A(n+1)$ stimmt.
Es gibt ja auch "falsche" Induktionsbeweise, die ganz lustig sind:
Behauptet wird, dass eine Aussage $A(n)$ stimme. Man kann dann in der Tat zeigen, dass, wenn $A(n)$ stimmt, dann auch $A(n+1)$ stimmt. D.h. hier würden alle Dominosteine nahe genug beieinander stehen, so dass, wenn einer fällt, auch alle darauffolgenden umfallen würden. Nur findet man dann überhaupt kein [mm] $n_0$, [/mm] so dass [mm] $A(n_0)$ [/mm] wahr wäre, d.h. keiner der Dominosteine kann als Startstein gewählt werden.
Beispiel:
$n+1 [mm] \le [/mm] n$ gilt für alle $n [mm] \in \IN$.
[/mm]
(Das ist offensichtlicher Unsinn. Dennoch: Wie sähe der Induktionsschritt im Induktionsbeweis aus?)
Induktionsvoraussetzung: Sei $n [mm] \in \IN$ [/mm] mit $n+1 [mm] \le [/mm] n$.
Induktionsschritt:
Zu zeigen ist, dass $(n+1)+1 [mm] \le [/mm] n+1$. Dies ist gleichwertig zu $n+1 [mm] \le [/mm] n$, was nach Induktionsvoraussetzung gilt.
Und dennoch haben wir keinen Induktionsbeweis, und der wird uns nicht gelingen, denn:
Die Suche nach dem "Startstein" scheitert:
Wir suchen nun ein [mm] $n_0 \in \IN$, [/mm] so dass [mm] $n_0+1 \le n_0$. [/mm] Wenn es so eines gäbe, dann wäre $1 [mm] \le [/mm] 0$. Widerspruch.
Konsequenz: Obwohl der Induktionsschritt beweisbar ist, stimmt die Aussage $A(n)$ für kein $n [mm] \in \IN$.
[/mm]
Genauso kann man sich ein Beispiel konstruieren, wo der Induktionsstart klappt, aber der Induktionsschritt nicht. D.h. wir wissen: Es gibt einen Stein, den man umwerfen kann, aber wir wissen nicht, wie "gut" der Abstand zwischen zwei Dominosteinen ist.
Beispiel:
Behauptung:
Es gilt [mm] $n^2 \le [/mm] 3n$ für alle $n [mm] \in \IN$.
[/mm]
Induktionsstart klappt für [mm] $n_0=1$ [/mm] oder [mm] $n_0=2$ [/mm] oder [mm] $n_0=3$, [/mm] aber der Induktionsschritt wird nicht beweisbar sein.
Es gibt auch noch andere Vorstellungsmöglichkeiten, wie man die vollständige Induktion erklären könnte. Mir selbst fällt da gerade die Idee ein, dass man es z.B. mit [mm] $|\IN|$ [/mm] vielen Lampen und Reihenschaltung erklären könnte, wobei eine Lampe, die leuchtet, dann jedenfalls anzeigt, dass die zugehörige Aussage stimmt usw.
Und vielleicht mal ein Beispiel, wo Du im Induktionsschritt auch wirklich siehst, dass die Induktionsvoraussetzung "gebraucht" wird:
Ich behaupte, dass für alle $n [mm] \in \IN$ [/mm] gilt:
[mm] $2^{n+1} \ge [/mm] 3*n$.
$n=1$: Die Aussage bedeutet dann, dass [mm] $2^2=4 \ge [/mm] 3*1=3$ gilt, das stimmt offensichtlich.
(D.h., wir werden mindestens den ersten Dominostein umwerfen können. Frage: Stehen die Dominosteine auch "nahe genug" beieinander, so dass alle auf den ersten folgenden Dominosteine umfallen werden?)
$n [mm] \mapsto [/mm] n+1$.
Sei $n [mm] \in \IN$ [/mm] mit [mm] $2^{n+1} \ge [/mm] 3*n$. Zu zeigen ist, dass dann auch
[mm] $2^{(n+1)+1} \ge [/mm] 3*(n+1)$ gilt.
Es gilt:
[mm] $2^{(n+1)+1}=2^{n+1}*2 \ge [/mm] (3*n)*2$ nach Induktionsvoraussetzung. Weil nun $(3*n)*2=6*n [mm] \ge [/mm] 3n+3$ für alle $n [mm] \in \IN$ [/mm] gilt (wie würdest Du das beweisen), folgt damit:
[mm] $2^{(n+1)+1}\ge [/mm] (3*n)*2=6n [mm] \ge [/mm] 3n+3=3*(n+1)$
Also:
Die Dominosteine stehen alle so dicht beieinander, so dass, wenn einer umfällt, alle darauffolgenden umfallen (das zeigt der Induktionsschritt). Wir dürfen den ersten - mit der Nummer $1$ - umschmeißen (das O.K. dazu haben wir erhalten, indem wir kontrolliert haben, dass $A(1)$ wirklich stimmt). Also fallen alle um, d.h. eine jede Aussage $A(n)$ mit einem $n [mm] \in \IN$ [/mm] ist wahr, wobei hier
$A(n)$: "Es gilt [mm] $2^{n+1} \ge [/mm] 3*n$" ($n [mm] \in \IN$)
[/mm]
definiert war.
Konsequenz aus dem, was oben steht:
Man darf bei (der obigen Methode der) Induktionsbeweise(n) i.a. weder auf den Induktionsstart noch auf den Beweis des Induktionsschrittes verzichten.
"Dominostein-Interpretation":
Wenn wir erreichen wollen, dass alle Dominosteine, die wir aufgestellt haben (derer seien es [mm] $|\IN|$ [/mm] Stück), fallen sollen, so müssen wir kontrollieren, dass sie alle auch "nahe genug beieinander" stehen (die Kontrolle ist geschehen, wenn wir den Induktionsschritt $n [mm] \mapsto [/mm] n+1$ gezeigt haben) und wir müssen den ersten Stein umwerfen können (das O.K. dazu bekommen wir, indem wir prüfen, dass die Aussage $A(1)$ auch stimmt). Denn was nützt es uns, wenn wir den ersten Stein umwerfen dürfen, aber nicht wissen, dass die Steine auch nahe genug beieinander stehen?
(Das wäre: Induktionsstart $A(1)$ gelingt, aber an dem Beweis des Induktionsschrittes $n [mm] \mapsto [/mm] n+1$ scheitern wir.)
Und was nützt es uns, zu wissen, dass die Dominosteine zwar alle "nahe genug" beieinander stehen, aber wir keinen "Startstein" haben, den wir umwerfen dürfen
(Das wäre: Der Induktionsschritt $n [mm] \mapsto [/mm] n+1$ klappt, aber $A(1)$ klappt nicht (eine Idee, wenigstens etwas damit zu ereichen:
Dann sucht man vll. ein anderes [mm] $n_0$, [/mm] so dass [mm] $A(n_0)$ [/mm] stimmt. Wenn wir so eins finden, heißt das dann, dass wir den [mm] $n_0$-ten [/mm] Stein umwerfen dürfen)).
Und vielleicht noch zu guter letzt nochmal zurück zu dem kleinen Gauß:
Behauptung:
$A(n)$: [mm] $1+...+n=\frac{n}{2}(n+1)$.
[/mm]
Induktionsstart: $n=1$
Dort steht dann, dass die Gleichung [mm] $1=\frac{1}{2}*(1+1)$ [/mm] gilt, und rechts steht [mm] $\frac{1}{2}*2$, [/mm] was ja in der Tat $=1$ ist.
$n [mm] \mapsto [/mm] n+1$:
Zu zeigen ist: [mm] $1+...+n+(n+1)=\frac{n+1}{2}*((n+1)+1)$ [/mm] bzw.
[mm] $1+...+n+(n+1)=\frac{n+1}{2}*(n+2)$.
[/mm]
Benutzt werden darf dafür, dass die I.V.
[mm] $(\*)$ $1+...+n=\frac{n}{2}(n+1)$ [/mm] gelten soll. Also:
Damit gilt
[mm] $\blue{1+...+n+(n+1)=\frac{n}{2}(n+1)+(n+1)}$ [/mm] wegen [mm] $(\*)$. [/mm] Es ist nun
[mm] $\red{1+...+n+(n+1)=\frac{n+1}{2}*(n+2)}$ [/mm] zu zeigen, und wir haben gesehen, dass wir
[mm] $\blue{1+...+n+(n+1)=\frac{n}{2}(n+1)+(n+1)}$
[/mm]
benutzen dürfen.
Wegen
[mm] $\blue{\frac{n}{2}(n+1)+(n+1)=1+...+n+(n+1)}=\red{1+...+n+(n+1)=\frac{n+1}{2}*(n+2)}$
[/mm]
gilt es nun nur, die Gleichheit
[mm] $\blue{\frac{n}{2}(n+1)+(n+1)}=\red{\frac{n+1}{2}*(n+2)}$
[/mm]
zu begründen. Das sieht man aber z.B. sofort ein, wenn man bei dem Term
[mm] $\blue{\frac{n}{2}(n+1)+(n+1)}$ [/mm] den Summand $(n+1)$ vorklammert.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:24 Mo 14.04.2008 | | Autor: | dau2 |
> Hallo,
>
> > > OK, beliebt ist der Anschauliche Vergleich mit einer
> > > Dominokette.
> > > Verfolgen wir diesen Ansatz, zumindest nutze ich ihn als
> > > begleitende Stütze.
> > > Auf die Rechtfertigung der Induktion mit den
> > Peano-Axiomen
> > > können wir jetzt denke ich verzichten, da diese sehr
> > > trockene Ansicht das Verständnis wohn nicht fördert.
> >
> > Sehr gute Entscheidung :)
> >
> > >
> > > Wir betrachten unsere Aussage [mm]A_n,[/mm] und wollen zeigen: [mm]A_n[/mm]
> > > ist wahr für alle [mm]n\in\IN[/mm]
> > > (Unsere Dominokette besteht aus den einzelnen "Steinen"
> > > [mm]A_n,[/mm] bewiesen ist, wer umfällt ;) Nun stoßen wir die Kette
> > > an:)
> > >
> > > Induktionsanfang:
> > > [mm]A_1[/mm] ist wahr. Diese Aussage zeigst du durch direktes
> > > Nachrechnen.
> > > Wir zeigen hier es gibt wenigstens eine natürliche
> Zahl
> > > für welche die Aussage stimmt.
> > >
> > > Induktionsvoraussetzung: (*)
> > > Sei [mm]n\in\IN[/mm] beliebig aber fest gewählt sodass [mm]A_n[/mm]
> > bewiesen
> > > ist
> > > ---
> > > Schnipp...Warum darf ich das sagen wenn [mm]A_n[/mm] nicht
> > bewiesen
> > > ist?
> >
> > Wird [mm]A_n[/mm] (wobei n eine gewählte Zahl ist) nicht durch den
> > Induktionsanfang zwangsläufig bewiesen?
> >
> >
> > > Nun ja, ich muss mein n eben so "wählen" DASS die Aussage
> > > schon bewiesen wurde für dieses n. Der Induktionsanfang
> > > garantiert mir das ich immer ein solches n wählen kann, im
> > > Notfall 1 :)
> > > ---
> > >
> > > Induktionsschritt:
> > > Hier wissen wir nach der Induktionsvoraussetzung dass [mm]A_n[/mm]
> > > für das "aktuelle" n korrekt ist. Daraus folgern wir die
> > > Aussage [mm]A_{n+1}[/mm]
> > > In deinem Beispiel zB ist hier zu zeigen dass
> > > KleinGauss(n+1) = KleinGauss(n)+ n+1
> > > [Die Abkürzung musste sein sry]
> > >
> > > Gelingt uns dies, haben wir die Menge der [mm]n\in\IN[/mm] für die
> > > [mm]A_n[/mm] stimmt um (n+1) ergänzt. Also dürften wir in (*) auch
> > > diese Zahl für n wählen, woraus wieder die nächste Zahl
> > > folgt usw....
> > > Wir haben eine Endlosschleife gestartet die unseren
> > Beweis
> > > auf ganz [mm]\IN[/mm] überträgt.
> > >
> > > Ich hoffe das war einigermaßen nachvollziehbar
> >
> >
> > Wäre es dann nicht besser am Ende zum Beweis des ganzen
> > sowas wie
> > 1 = 1 stehen zu haben, also etwas was auch optisch auf
> den
> > ersten Blick gleich ist?
>
> wenn man - unter Verwendung der Induktionsvoraussetung -
> nur äquivalente Umformungen macht, wird das wohl gehen
> (weil man dann ja sogar zeigt: [mm]A(n) \mbox{ ist wahr} \gdw A(n+1) \mbox{ ist wahr}[/mm]).
> Aber Du hast ja zwei Dinge zu zeigen:
>
> 1.) Die Aussage [mm]A(1)[/mm] ist korrekt.
>
> 2.) Wenn es ein [mm]n \in \IN[/mm] gibt, so dass [mm]A(n)[/mm] stimmt, dann
> stimmt auch [mm]A(n+1)[/mm].
Dann könnte ich ja gleich nach A(n) sagen das ich Fertig bin, warum sich mit A(n+1) aufhalten wenn es sowieso richtig ist?
Danke erstmal für deine ausführliche Erklärung, das muss ich mir morgen nochmal in Ruhe durchlesen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:12 Mo 14.04.2008 | | Autor: | Marcel |
Hallo,
> > Aber Du hast ja zwei Dinge zu zeigen:
> >
> > 1.) Die Aussage [mm]A(1)[/mm] ist korrekt.
> >
> > 2.) Wenn es ein [mm]n \in \IN[/mm] gibt, so dass [mm]A(n)[/mm] stimmt, dann
> > stimmt auch [mm]A(n+1)[/mm].
>
> Dann könnte ich ja gleich nach A(n) sagen das ich Fertig
> bin, warum sich mit A(n+1) aufhalten wenn es sowieso
> richtig ist?
das verstehe ich nicht. Im Induktionsschritt $n [mm] \mapsto [/mm] n+1$ hast Du zu zeigen: Wenn $A(n)$ als wahr erkannt wurde, dann gilt auch $A(n+1)$. Nur, wenn der Beweis des Induktionsschrittes gelingt, dann weißt Du, dass "die Dominosteine so nahe beieinander stehen, dass, wenn einer fällt, auch alle darauffolgenden umfallen". Wenn Du den Induktionsschritt nicht beweisen kannst, bringt es Dir "fast" gar nichts, eine Aussage [mm] $A(n_0)$ [/mm] zu beweisen, denn dann weißt Du nur, dass diese Aussage [mm] $A(n_0)$ [/mm] stimmt, weil der Dominostein mit der Nummer [mm] $n_0$ [/mm] umgefallen ist. Du weißt hier nicht, wie gut die Dominosteine dann beieinander stehen.
Als Beispiel:
Ich behaupte wieder eine offensichtlich falsche Aussage, nämlich:
[mm] $(-1)^n [/mm] < 0$ für alle $n [mm] \in \IN$.
[/mm]
Man sieht hier sehr leicht, dass die Aussage nur für alle ungerade $n [mm] \in \IN$ [/mm] gilt. Der Induktionsstart für $n=1$ würde wegen [mm] $(-1)^1=-1 [/mm] < 0$ klappen, d.h., wir dürften den ersten Dominostein umwerfen.
Der Induktionsschritt, der ausformuliert hieße:
[mm] $(\*)$ [/mm] Wenn [mm] $(-1)^n [/mm] < 0$ ist, dann ist auch [mm] $(-1)^{n+1} [/mm] < 0$
läßt sich aber nicht beweisen. Für [mm] $(-1)^{n+1}$ [/mm] gilt nämlich folgendes:
[mm] $(-1)^{n+1}=(-1)*(-1)^n$, [/mm] wobei $-1 < 0$ sicherlich gilt und [mm] $(-1)^n [/mm] < 0$ nach I.V. wäre, also wäre:
[mm] $(-1)^{n+1}=(-1)*(-1)^n [/mm] > 0$, da die letzten beiden Faktoren beide $< 0$ wären (und das Produkt zweier echt negativer Zahlen ist echt positiv).
Was zeigt uns diese Art vom Scheitern des Induktionsbeweises hier nun?
Weil $A(1)$ gilt, dürfen wir den ersten Dominostein umwerfen. Aber was bringt uns das? Nichts, einzig, dass die Aussage $A(1)$ als wahr erkannt wurde. Denn weil der Beweis des Induktionsschrittes scheitert, haben wir sozusagen eine "Unkenntnis" darüber, ob die Dominosteine "nahe genug" beieinander stehen. Wäre uns der Beweis des Induktionsschrittes gelungen, so wären hier alle Dominosteine nahe genug beieinander, d.h. das Umschmeißen des ersten hätte zur Konsequenz, dass alle umfallen würden und wir eine jede Aussage $A(n)$ als wahr erkennen würden.
Da uns der Beweis des Induktionsschrittes nicht gelungen ist, wissen wir nicht, "wie gut" der Abstand zwischen den einzelnen Dominosteinen ist. Wenn wir $A(1)$ umschmeißen, haben wir keine Kenntnis, ob dann $A(2)$ umfällt oder nicht. Selbst, wenn wir wüßten, dass wir $A(2)$ umschmeißen dürften (was wir in dem obigen Falle eh nicht tun dürften, da die Aussage $A(2)$ hieße, dass [mm] $(-1)^2 [/mm] < 0$, was gleichwertig zu $1 < 0$ wäre, was offensichtlich falsch ist) so wüßten wir nicht, ob dann $A(3)$ umfallen würde...
Ich gebe Dir auch mal eine schöne Aufgabe, wo man auch sieht, wie das Induktionsprinzip greift (ich hoffe jedenfalls, dass Du es so wie ich auch siehst  ):
Ich behaupte:
[mm] $n^2-19n+60 \ge [/mm] 0$ gilt für alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge [/mm] 15$.
Führe mal den Induktionsbeweis:
Der Induktionsstart wird für $n=15$ funktionieren, der Induktionsschritt auch.
Jetzt kann ich als Zusatzfrage stellen:
Für genau welche $n [mm] \in \IN$ [/mm] gilt [mm] $n^2-19n+60 \ge [/mm] 0$?
Oben haben wir dann gesehen, dass jedenfalls ab dem 15en Stein alle umfallen. Wenn ich jetzt sagen will, dass genau die umgefallenen Steine kennzeichnen sollen, dass die zugehörige Aussage gilt:
Was habe ich dann bei den ersten 14 Steinen noch zu tun?
Und wenn ich nun
[mm] $n^2-19n+60 \ge [/mm] 0$ gilt für alle $n [mm] \in \IN$ [/mm]
behaupten würde, würde der Induktionsstart auch gelingen, aber der Beweis des Induktionsschrittes würde uns so nicht gelingen.
Wenn ich nun generell gucke:
Für welche $n [mm] \in \IN$ [/mm] gilt denn schon, dass, wenn $A(n)$ als wahr erkannt wurde, dann auch $A(n+1)$ gilt, so kann ich dies' sogar schon für alle $n [mm] \ge [/mm] 9$ beweisen:
Sei $n [mm] \in \IN$ [/mm] mit $n [mm] \ge [/mm] 9$.
(I) Es gelte [mm] $\blue{n^2-19n+60 \ge 0}$.
[/mm]
Dann gilt:
[mm] $(n+1)^2-19(n+1)+60=\blue{n^2}+2n+1\blue{-19n}-19\blue{+60} \ge [/mm] 2n+1-19$ nach (I), und für alle $n [mm] \ge [/mm] 9$ ist $2n+1-19 [mm] \ge [/mm] 19-19=0$, also auch
[mm] $(n+1)^2-19(n+1)+60 \ge [/mm] 0$
Was wissen wir also hier bei der Aussage $A(n)$ ($n [mm] \in \IN$):
[/mm]
[mm] $n^2-19n+1 \ge [/mm] 0$
über die Dominosteine?
Wir wissen:
Über den Abstand der Dominosteine von Nummer $1,...,9$ wissen wir nichts. D.h., wenn wir einen von denen umschmeißen, haben wir erstmal keine Ahnung, was mit dem darauffolgenden passieren wird.
Über den Abstand der Dominosteine ab der Nummer 9 wissen wir:
Wenn wir einen von denen umschmeißen dürfen, dann werden alle darauffolgenden umfallen, sie stehen "nahe genug" beieinander. Warum kann ich dann obiges nicht zu:
[mm] $n^2-19n+60 \ge [/mm] 0$ gilt für alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge [/mm] 9$
verschärfen? Ganz einfach:
Die Aussage $A(9)$ ist falsch, d.h., wir dürfen den 9en Stein gar nicht umwerfen. Wenn wir nun ab dem 9en Stein den ersten suchen, den wir umwerfen dürfen, so ist das der 15e Stein.
(Was man allerdings machen kann:
[mm] $n^2-19n+60 \ge [/mm] 0$ gilt für alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge [/mm] 300$
kann man genausogut beweisen. Es wäre dann halt nur nicht im obigen Sinne die "stärkste" Aussage, d.h. man könnte sie verbessern.)
Gruß,
Marcel
|
|
|
|
