vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:51 Sa 27.04.2013 | | Autor: | Diahara |
| Aufgabe | Beweisen Sie mittels vollständiger Induktion die folgende Aussage:
[mm] n!\le n^{n-1} [/mm] für alle n [mm] \ge [/mm] 1 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Die Aufgabe stammt aus einem Übungsblatt zu LA1, bei dem der Abgabetermin bereits verstrichen ist.
Um die Behauptung zu beweisen, bin ich so vorgegangen:
Induktionsanfang: n=1
[mm] 1!\le 1^{1-1} \gdw 1!\le 1^0 \gdw 1!\le [/mm] 1 ist wahr für n=1.
Induktionsvoraussetzung:
Für [mm] 1\le k\ge [/mm] n gilt [mm] k!\le k^{k-1}.
[/mm]
Ich will also beweisen, dass wenn die Aussage für k wahr ist, auch die Aussage für k+1 wahr sein muss.
Induktionsschritt:
n -> n+1 Zu beweisen ist: [mm] (n+1)!\le (n+1)^{n+1-1}
[/mm]
Durch umformen komme ich immer auf:
[mm] n!*(n+1)\le (n+1)^n [/mm] .
Jetzt bin ich mir an dieser Stelle nicht sicher, ob der Schritt der richtige ist und dass ich das mit der vollständigen Induktion wirklich verstanden habe.
Denn zeigen wollte ich doch eigentlich unter der Voraussetzung das k gilt, dass [mm] (n+2)!\le (n+2)^{n+1} [/mm] oder anders geschrieben, dass
[mm] (n+1+1)!\le (n+2)^n+(n+2)^1 [/mm] wahr ist.
Darauf kann ich aber durch den von mir gewählten Induktionsschritt nicht schließen, da ich durch Umformung nicht darauf komme.
Oder kann ich wegen der Ungleichung ohne weitere Erläuterung darauf schließen, dass das (n+2)-fache von (n+1)! bei jedem weiteren n nicht so schnell steigt (also kleiner ist), als das (n+2)-fache der Potenz n zur Basis (n+2)?
Ich freue mich über jeden Tipp.
|
|
| |
|
Hallo Diahara, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Dir fehlt da nur eine einzige Überlegung, meine ich.
> Beweisen Sie mittels vollständiger Induktion die folgende
> Aussage:
>
> [mm]n!\le n^{n-1}[/mm] für alle n [mm]\ge[/mm] 1
>
> Die Aufgabe stammt aus einem Übungsblatt zu LA1, bei dem
> der Abgabetermin bereits verstrichen ist.
Wir würden Dir auch helfen, wenn der Abgabetermin noch aussteht. Allerdings versuchen wir normalerweise, Dir nur soviel Hinweise zu geben, dass Du die Lösung selbst finden kannst. Das ist hier nicht ganz einfach. 
> Um die Behauptung zu beweisen, bin ich so vorgegangen:
> Induktionsanfang: n=1
> [mm]1!\le 1^{1-1} \gdw 1!\le 1^0 \gdw 1!\le[/mm] 1 ist wahr
> für n=1.
![[ok]](/images/smileys/ok.gif "[ok]")
> Induktionsvoraussetzung:
> Für [mm]1\le k\blue{\le}n[/mm] gilt [mm]k!\le k^{k-1}.[/mm]
edit: da war ein Relationszeichen falsch. Ich habs für einen Tippfehler gehalten und nicht korrigiert. Jetzt aber.
> Ich will also
> beweisen, dass wenn die Aussage für k wahr ist, auch die
> Aussage für k+1 wahr sein muss.
Du meinst n, nicht k. Oder?
Genau. Das ist der Plan.
> Induktionsschritt:
> n -> n+1 Zu beweisen ist: [mm](n 1)!\le (n 1)^{n 1-1}[/mm]
>
> Durch umformen komme ich immer auf:
> [mm]n!*(n 1)\le (n 1)^n[/mm] .
Ok, da ist ja noch nicht viel umgeformt. Aber es ist ok und ein Schritt auf dem nötigen Weg.
> Jetzt bin ich mir an dieser Stelle nicht sicher, ob der
> Schritt der richtige ist und dass ich das mit der
> vollständigen Induktion wirklich verstanden habe.
>
> Denn zeigen wollte ich doch eigentlich unter der
> Voraussetzung das k gilt, dass [mm](n 2)!\le (n 2)^{n 1}[/mm] oder
> anders geschrieben, dass
> [mm](n 1 1)!\le (n 2)^n (n 2)^1[/mm] wahr ist.
Nein, das wolltest Du nicht. Das wäre ja gleich zwei Schritte weiter. Zu beweisen ist, was Du oben unter "Induktionsschritt" geschrieben hast, also die Behauptung auf n+1 angewandt.
> Darauf kann ich aber durch den von mir gewählten
> Induktionsschritt nicht schließen, da ich durch Umformung
> nicht darauf komme.
Du willst vielleicht nur zuviel... Für n+2 ist hier ohne weiteres nichts zu folgern.
> Oder kann ich wegen der Ungleichung ohne weitere
> Erläuterung darauf schließen, dass das (n+2)-fache von
> (n+1)! bei jedem weiteren n nicht so schnell steigt (also
> kleiner ist), als das (n+2)-fache der Potenz n zur Basis
> (n+2)?
Nein, das kannst Du bestimmt nicht.
> Ich freue mich über jeden Tipp.
Na dann. Du hattest
[mm] n!(n+1)\le(n+1)^n
[/mm]
Kürzen wir mal (n+1). Dann bleibt
[mm] n!\le(n+1)^{n-1}
[/mm]
Oft hilft ein faktorenweiser Vergleich weiter. Auf den ersten Blick hilft das hier noch nicht. Links stehen n Faktoren, rechts n-1.
Wenn jetzt [mm] n\ge2 [/mm] wäre, hätte man kein Problem, denn links ist einer der Faktoren ja 1. Dann könnte man schreiben:
[mm] n!=\produkt_{k=2}^{n}\blue{k}\le(n+1)^{n-1}
[/mm]
Hm. Da fehlte noch etwas Entscheidendes im Produkt...
Links n-1 Faktoren, rechts auch, und jeder der linken ist kleiner als n+1.
Da gibts nur eine Lösung. Man zeigt den Induktionsanfang halt gleich für n=1 und n=2. Ab da klappts.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:38 Sa 27.04.2013 | | Autor: | Marcel |
Hallo reverend,
> Links n-1 Faktoren, rechts auch, und jeder der linken ist
> kleiner als n+1.
>
> Da gibts nur eine Lösung. Man zeigt den Induktionsanfang
> halt gleich für n=1 und n=2. Ab da klappts.
brauchst Du nicht. Überleg' Dir mal, "mit welchem Schritt" Du einen Faktor
verloren hast! Übrigens habe ich wieder die Befürchtung, dass hier ein
Beweis der Richtung: $B [mm] \Rightarrow [/mm] A$ stattfinden wird, obwohl $A [mm] \Rightarrow [/mm] B$ gezeigt werden soll.
Oftmals wird das "insofern" unkritisiert gelassen, als dass sich die [mm] $\Rightarrow$'s [/mm] auch
einfach in [mm] $\iff$'s [/mm] umschreiben lassen ^^ (was aber eigentlich immer
überlegt werden muss).
Was ich genauer meine, findet man bspw. hier (klick!)
Um's mal kurz und bündig zu machen:
Im Beweisschritt nutzt man, dass man BENUTZEN DARF $n! [mm] \le n^{n-1}$ [/mm] für ein $n [mm] \in \IN\,.$ [/mm]
Aus diesem Wissen will man folgern dürfen, dass $(n+1)! [mm] \le (n+1)^n$ [/mm] auch gültig
sein muss.
Bei $(n+1)! [mm] \le (n+1)^n \iff [/mm] n! [mm] \le (n+1)^{n-1}$ [/mm] interessiert uns eigentlich auch gar nicht
die Folgerungsrichtung [mm] $\Longrightarrow$ [/mm] - sondern uns interessiert vor allem, dass
[mm] $\Longleftarrow$ [/mm] gelten sollte! Denn dann reicht es, für unser [mm] $n\,,$ [/mm] dass ja
auch $n! [mm] \le n^{n-1}$ [/mm] erfüllt, zu beweisen, dass dieses auch $n! [mm] \le (n+1)^{n-1}$ [/mm] erfüllt
und wir sind fertig!
P.S. Ich suche und korrigiere gerade noch die unzähligen Verschreiber, die
mir hier passiert sind ^^
Hoffentlich stimmt's nun ^^
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:54 Sa 27.04.2013 | | Autor: | reverend |
Hallo Marcel,
ok, an zwei Stellen war ich nicht gründlich genug. Die habe ich jetzt mal editiert.
> > Links n-1 Faktoren, rechts auch, und jeder der linken ist
> > kleiner als n+1.
> >
> > Da gibts nur eine Lösung. Man zeigt den Induktionsanfang
> > halt gleich für n=1 und n=2. Ab da klappts.
>
> brauchst Du nicht. Überleg' Dir mal, "mit welchem Schritt"
> Du einen Faktor
> verloren hast! Übrigens habe ich wieder die Befürchtung,
> dass hier ein
> Beweis der Richtung: [mm]B \Rightarrow A[/mm] stattfinden wird,
> obwohl [mm]A \Rightarrow B[/mm] gezeigt werden soll.
> Oftmals wird das "insofern" unkritisiert gelassen, als
> dass sich die [mm]\Rightarrow[/mm]'s auch
> einfach in [mm]\iff[/mm]'s umschreiben lassen ^^ (was aber
> eigentlich immer
> überlegt werden muss).
>
> Was ich genauer meine, findet man bspw.
> hier (klick!)
>
> Um's mal kurz und bündig zu machen:
> Im Beweisschritt nutzt man, dass man BENUTZEN DARF [mm]n! \le n^{n-1}[/mm]
> für ein [mm]n \in \IN\,.[/mm]
> Aus diesem Wissen will man folgern dürfen, dass [mm](n 1)! \le (n 1)^n[/mm]
> auch gültig
> sein muss.
>
> Bei [mm](n 1)! \le (n 1)^n \iff n! \le (n 1)^{n-1}[/mm] interessiert
> uns eigentlich auch gar nicht
> die Folgerungsrichtung [mm]\Longrightarrow[/mm] - sondern uns
> interessiert vor allem, dass
> [mm]\Longleftarrow[/mm] gelten sollte! Denn dann reicht es, für
> unser [mm]n\,,[/mm] dass ja
> auch [mm]n! \le n^{n-1}[/mm] erfüllt, zu beweisen, dass dieses
> auch [mm]n! \le (n 1)^{n-1}[/mm] erfüllt
> und wir sind fertig!
Ich gestehe, ich kann Dir ausnahmsweise mal nicht folgen, obwohl Du sonst sehr scharfsinnig und verständlich logische Fehler aufzeigst. Hier sehe ich nach wie vor keinen. Warum sollte man den Faktor 1 nicht streichen? Und warum müsste man dann nicht erst bei [mm] n\ge2 [/mm] beginnen?
> P.S. Ich suche und korrigiere gerade noch die unzähligen
> Verschreiber, die
> mir hier passiert sind ^^
Och, wenn sie nicht sinnentstellend sind, würde ich sie lassen. Ich bin sonst immer geneigt, alle Revisionen zu lesen...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:04 Sa 27.04.2013 | | Autor: | Marcel |
Hallo reverend,
> Hallo Marcel,
>
> ok, an zwei Stellen war ich nicht gründlich genug. Die
> habe ich jetzt mal editiert.
>
> > > Links n-1 Faktoren, rechts auch, und jeder der linken ist
> > > kleiner als n+1.
> > >
> > > Da gibts nur eine Lösung. Man zeigt den
> Induktionsanfang
> > > halt gleich für n=1 und n=2. Ab da klappts.
> >
> > brauchst Du nicht. Überleg' Dir mal, "mit welchem
> Schritt"
> > Du einen Faktor
> > verloren hast! Übrigens habe ich wieder die
> Befürchtung,
> > dass hier ein
> > Beweis der Richtung: [mm]B \Rightarrow A[/mm] stattfinden wird,
> > obwohl [mm]A \Rightarrow B[/mm] gezeigt werden soll.
> > Oftmals wird das "insofern" unkritisiert gelassen, als
> > dass sich die [mm]\Rightarrow[/mm]'s auch
> > einfach in [mm]\iff[/mm]'s umschreiben lassen ^^ (was aber
> > eigentlich immer
> > überlegt werden muss).
> >
> > Was ich genauer meine, findet man bspw.
> > hier (klick!)
> >
> > Um's mal kurz und bündig zu machen:
> > Im Beweisschritt nutzt man, dass man BENUTZEN DARF [mm]n! \le n^{n-1}[/mm]
>
> > für ein [mm]n \in \IN\,.[/mm]
> > Aus diesem Wissen will man
> folgern dürfen, dass [mm](n 1)! \le (n 1)^n[/mm]
> > auch gültig
> > sein muss.
> >
> > Bei [mm](n 1)! \le (n 1)^n \iff n! \le (n 1)^{n-1}[/mm]
> interessiert
> > uns eigentlich auch gar nicht
> > die Folgerungsrichtung [mm]\Longrightarrow[/mm] - sondern uns
> > interessiert vor allem, dass
> > [mm]\Longleftarrow[/mm] gelten sollte! Denn dann reicht es, für
> > unser [mm]n\,,[/mm] dass ja
> > auch [mm]n! \le n^{n-1}[/mm] erfüllt, zu beweisen, dass dieses
> > auch [mm]n! \le (n 1)^{n-1}[/mm] erfüllt
> > und wir sind fertig!
>
> Ich gestehe, ich kann Dir ausnahmsweise mal nicht folgen,
> obwohl Du sonst sehr scharfsinnig und verständlich
> logische Fehler aufzeigst. Hier sehe ich nach wie vor
> keinen. Warum sollte man den Faktor 1 nicht streichen? Und
> warum müsste man dann nicht erst bei [mm]n\ge2[/mm] beginnen?
ich habe mal aufgeschrieben, wie man den Induktionsbeweis "sauber"
führen kann, 'obwohl' man mit [mm] $n=1\,$ [/mm] anfängt!
> > P.S. Ich suche und korrigiere gerade noch die unzähligen
> > Verschreiber, die
> > mir hier passiert sind ^^
>
> Och, wenn sie nicht sinnentstellend sind, würde ich sie
> lassen. Ich bin sonst immer geneigt, alle Revisionen zu
> lesen...
Sie waren falsch, sowas wie: Wenn ich [mm] $n^n$ [/mm] schreibe, aber [mm] $(n+1)^{n-1}$ [/mm] meine...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:22 Sa 27.04.2013 | | Autor: | reverend |
Hallo Marcel,
> ich habe mal aufgeschrieben, wie man den Induktionsbeweis
> "sauber"
> führen kann, 'obwohl' man mit [mm]n=1\,[/mm] anfängt!
Das sehe ich gerade. Ich lese es tagsüber nochmal; im Moment bin ich nicht mehr so recht aufnahmefähig und muss auch noch eine Druckvorlage auf den Weg bringen, damit jemand anders morgens damit weiterarbeiten kann...
> > > P.S. Ich suche und korrigiere gerade noch die unzähligen
> > > Verschreiber, die
> > > mir hier passiert sind ^^
> >
> > Och, wenn sie nicht sinnentstellend sind, würde ich sie
> > lassen. Ich bin sonst immer geneigt, alle Revisionen zu
> > lesen...
>
> Sie waren falsch, sowas wie: Wenn ich [mm]n^n[/mm] schreibe, aber
> [mm](n 1)^{n-1}[/mm] meine...
Ja, das ist sinnentstellend. Passiert mir leider ständig. Da sind Revisionen dringend empfehlenswert.
Gute Nacht!
reverend
PS: Mir ist egal, wie lange du noch arbeitest. Ich habe gerade eine Asymptote gefunden, die sich meinem Bett nähert. 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:49 Sa 27.04.2013 | | Autor: | Diahara |
Hallo reverend,
vielen Dank für die Hilfe. Ich hatte auf meinem "Schmierblatt" war schon den Induktionsanfang für n=2 geschrieben, aber den Gedanken nicht weiter verfolgt. Jetzt ist alles klar.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:33 Sa 27.04.2013 | | Autor: | Marcel |
Hallo Diahara,
irgendwie scheint mir der Formeleditor momentan wirklich einiges an Formeln
zu zerschießen (jedenfalls bei reverends Zitaten), aber mal kurz:
> Für [mm]1\le k\ge[/mm] n
Das [mm] $\ge$ [/mm] hier sollte sicher ein [mm] $\le$ [/mm] sein, ansonsten sollte man "solch' eine
Ungleichungskette" niemals so schreiben ^^
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:02 Sa 27.04.2013 | | Autor: | Marcel |
Hallo,
die Induktion klappt mit I.A. [mm] $n=1\,$ [/mm] durchaus:
Für $n=1$ gilt offenbar $n!=1!=1 [mm] \le 1^0=n^{n-1}\,.$
[/mm]
Induktionsschritt $n [mm] \to [/mm] n+1:$
I.V.: Sei $n [mm] \in \IN$ [/mm] mit $n! [mm] \le n^{n-1}\,.$ [/mm] (Dass es solch' eines gibt, haben
wir ja gerade im I.A. gezeigt!)
Zu zeigen ist, dass dann $(n+1)! [mm] \le (n+1)^n$ [/mm] gilt. Wegen $(n+1)! [mm] \le (n+1)^n \Longleftarrow [/mm] n! [mm] \le (n+1)^{n-1}$ [/mm]
(tatsächlich gilt hier [mm] $\iff$, [/mm] aber [mm] $\Longleftarrow$ [/mm] ist die "interessante" Folgerungsrichtung
für uns!)
reicht es wiederum, zu beweisen, dass das $n [mm] \in \IN$ [/mm] mit $n! [mm] \le n^{n-1}$ [/mm] auch $n! [mm] \le (n+1)^{n-1}$ [/mm] erfüllt.
Wie begründet man also $n! [mm] \le n^{n-1} \Longrightarrow [/mm] n! [mm] \le (n+1)^{n-1}$?
[/mm]
Idee: Versuche, zu beweisen/begründen, dass (für unser $n [mm] \ge [/mm] 1$ mit $n! [mm] \le n^{n-1}$) [/mm] auch
[mm] $$n^{n-1} \le (n+1)^{n-1}$$
[/mm]
gilt. Tipp (auch dieser wäre zu beweisen!): Für $a,b > [mm] 0\,$ [/mm] und $m [mm] \in \IN$ [/mm] gilt
[mm] $a^m [/mm] < [mm] b^m \iff [/mm] (b/a) > [mm] 1\,.$
[/mm]
("Besser" vielleicht: [mm] $a^m \le b^m \iff [/mm] (b/a) [mm] \ge [/mm] 1$ - hierbei kann auch $m [mm] \in \IN_0$ [/mm] sein!)
P.S. "Illustration" des Induktionsschrittes [mm] $\red{n}=1 \to \blue{n+1}=2:$
[/mm]
Es gilt [mm] $\red{\text{1}}! \le \red{\text{1}}^{\red{\text{1}}\;\;\;-1}\,.$ [/mm] Wegen [mm] $\red{\text{1}}^{\red{\text{1}}\;\;\;-1} \le (\blue{\text{2}})^{\red{\text{1}}\;\;\;-1}$ [/mm] folgt
[mm] $$\red{\text{1}}!*(\blue{\text{2}}) \le \red{\text{1}}^{\red{\text{1}}\;\;\;-1}*(\blue{\text{2}}) \le (\blue{\text{2}})^{\red{\text{1}}\;\;\;-1}*(\blue{\text{2}})=(\blue{\text{2}})^{(\blue{\text{2}})\;\;\;-1}\,.$$ [/mm]
Tipp: Ersetze [mm] $\red{1}$ [/mm] wieder durch [mm] $n\,$ [/mm] und [mm] $\blue{2}$ [/mm] durch [mm] $n+1\,.$ [/mm] Dann siehst Du den
Induktionsschritt allgemein!!! (Beachte aber, dass die schwarze 1
in den Exponenten nicht ersetzt werden soll!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:08 Sa 27.04.2013 | | Autor: | Diahara |
Hallo Marcel,
vielen Dank für die ausführliche Erklärung zum Beweis durch vollständige Induktion von
n! [mm] \le n^{n-1} [/mm] für alle [mm] n\ge1 [/mm] .
Und bis zu Deiner "Illustration" n -> n+1 dachte ich auch, ich hätte es jetzt, aber beim Nachvollziehen des allgemeinen Induktionsschrittes verstehe ich noch etwas nicht:
Die Behauptung für n=1 (siehe I.A.) gilt.
Da
(Behauptung für n) [mm] \le [/mm] (Behauptung für n+1), folgt [mm] \le [/mm] (Behauptung für n+2)
[mm] \underbrace{\red{\text{1}}!\cdot{}(\blue{\text{2}}) \le \red{\text{1}}^{\red{\text{1}}\;\;\;-1}\cdot{}(\blue{\text{2}}) }_{
in Beh. (n+1) eingesetzt}\le \underbrace{(\blue{\text{2}})^{\red{\text{1}}\;\;\;-1}\cdot{}(\blue{\text{2}})}_{n+2} =\underbrace{(\blue{\text{2}})^{(\blue{\text{2}})\;\;\;-1}\,}_{\underbrace{(n+1)^{n+1-1}}_{Ziel?}}
[/mm]
.
Meinst Du damit:
Wenn die Behauptung für n wahr ist (I.A.) und auch für n+1 gilt (I.S. n nach n+1), dann muss sie auch für n+2 und somit für jedes weitere n wahr sein?
Ich gebe zu, dass es vielleicht albern ist, aber irgendwie habe ich immer den Eindruck, dass ich mich im Kreis drehe.
Denn manchmal habe ich die Begründung geliefert, ohne zu merken, das das alles war. Das deutet doch darauf hin, dass ich irgendwo auf dem Weg nicht mehr weiß, was ich will.
Kann ich mir denn dann vorher überlegen, wie mein Ziel aussehen soll, damit ich weiß, wann ich es erreicht habe? omg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:57 Sa 27.04.2013 | | Autor: | Marcel |
Hallo Diahara,
> Hallo Marcel,
>
> vielen Dank für die ausführliche Erklärung zum Beweis
> durch vollständige Induktion von
> n! [mm]\le n^{n-1}[/mm] für alle [mm]n\ge1[/mm] .
>
> Und bis zu Deiner "Illustration" n -> n+1 dachte ich auch,
> ich hätte es jetzt, aber beim Nachvollziehen des
> allgemeinen Induktionsschrittes verstehe ich noch etwas
> nicht:
>
> Die Behauptung für n=1 (siehe I.A.) gilt.
> Da
> (Behauptung für n) [mm]\le[/mm] (Behauptung für n+1), folgt [mm]\le[/mm]
> (Behauptung für n+2)
> [mm]\underbrace{\red{\text{1}}!\cdot{}(\blue{\text{2}}) \le \red{\text{1}}^{\red{\text{1}}\;\;\;-1}\cdot{}(\blue{\text{2}}) }_{
in Beh. (n+1) eingesetzt}\le \underbrace{(\blue{\text{2}})^{\red{\text{1}}\;\;\;-1}\cdot{}(\blue{\text{2}})}_{n+2} =\underbrace{(\blue{\text{2}})^{(\blue{\text{2}})\;\;\;-1}\,}_{\underbrace{(n+1)^{n+1-1}}_{Ziel?}}[/mm]
>
> .
>
> Meinst Du damit:
> Wenn die Behauptung für n wahr ist (I.A.) und auch für
> n+1 gilt (I.S. n nach n+1), dann muss sie auch für n+2 und
> somit für jedes weitere n wahr sein?
die Illustration ist doch nur eine Illustration.
> Ich gebe zu, dass es vielleicht albern ist, aber irgendwie
> habe ich immer den Eindruck, dass ich mich im Kreis drehe.
> Denn manchmal habe ich die Begründung geliefert, ohne zu
> merken, das das alles war. Das deutet doch darauf hin, dass
> ich irgendwo auf dem Weg nicht mehr weiß, was ich will.
> Kann ich mir denn dann vorher überlegen, wie mein Ziel
> aussehen soll, damit ich weiß, wann ich es erreicht habe?
Was ist denn Idee des Induktionsbeweises? Man hat Aussagen [mm] $A(n)\,$ [/mm] für
jedes $n [mm] \in \IN_0\,.$
[/mm]
Nun will man zeigen: [mm] $A(n)\,$ [/mm] gilt für alle $n [mm] \in \IN_0$ [/mm] mit $n [mm] \ge n_0\,.$
[/mm]
Induktionsanfang: Man zeigt: [mm] $A(n_0)$ [/mm] ist wahr.
Der Induktionsschritt zeigt bzw. soll zeigen:
Wenn $n [mm] \in \IN_0$ [/mm] mit $n [mm] \ge n_0$ [/mm] so ist, dass [mm] $A(n)\,$ [/mm] gilt, so folgt, dass dann
auch $A(n+1)$ gilt.
D.h., was man dort insgesamt macht, ist (für alle natürliche $n [mm] \ge n_0$):
[/mm]
[mm] $A(n)\,$ [/mm] ist wahr und im Induktionsschritt wird bewiesen, dass die Folgerung
$A(n) [mm] \Longrightarrow [/mm] A(n+1)$ (jedenfalls für natürliche $n [mm] \ge n_0$) [/mm] wahr ist, so liefert
das zusammen, dass [mm] $A(n+1)\,$ [/mm] dann auch wahr ist.
Man kann sich das auch einfach mit Logik überlegen:
Wenn man $A(n) [mm] \Longrightarrow [/mm] A(n+1)$ bewiesen hat, so weiß man, dass
[mm] $\neg [/mm] A(n) [mm] \vee [/mm] A(n+1)$ wahr ist.
Wenn nun [mm] $A(n)\,$ [/mm] wahr ist - wir schreiben nun dafür nur [mm] $A(n)\,$ [/mm] (wir würden
[mm] $\neg [/mm] A(n)$ schreiben, wenn [mm] $A(n)\,$ [/mm] falsch wäre),
so bedeutet
$A(n)$ [mm] $\wedge$ [/mm] $(A(n) [mm] \Longrightarrow [/mm] A(n+1))$
doch nichts anderes als
($A(n)$ [mm] $\wedge$ $(\neg [/mm] A(n) [mm] \vee [/mm] A(n+1))$).
Die Aussage
($A(n)$ [mm] $\wedge$ $(\neg [/mm] A(n) [mm] \vee [/mm] A(n+1))$)
kann aber nur noch genau dann wahr sein, wenn [mm] $A(n+1)\,,$ [/mm] d.h. wenn [mm] $A(n+1)\,$ [/mm]
wahr ist, denn sie ist doch gleichbedeutend mit
[mm] ($\red{(}A(n) \wedge \neg A(n)\red{)}$ $\vee$ $\red{(}A(n)\wedge A(n+1)\red{)}$)
[/mm]
und damit zu
[mm] $A(n)\wedge A(n+1)\,,$
[/mm]
und [mm] $A(n)\,$ [/mm] ist hier ja schon als wahr erkannt!
Zusammenfassend: Im Induktionsanfang zeigt man, dass [mm] $A(n_0)$ [/mm] wahr ist.
Im Induktionsschritt zeigt man, dass die Folgerung $A(n) [mm] \Longrightarrow A(n+1)\,$ [/mm] wahr
ist (für alle $n [mm] \ge n_0$ [/mm] jedenfalls).
Nur BEIDES ZUSAMMEN liefert dann, dass [mm] $A(n)\,$ [/mm] für alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge n_0$ [/mm]
wahr ist.
Denn dann kann man so schließen:
1.)
[mm] $A(n_0)$ [/mm] ist wahr. Weil die Folgerung [mm] $A(n_0) \Longrightarrow A(n_0+1)$ [/mm] gilt, liefert
[mm] $A(n_0) \wedge \red{(}A(n_0) \Longrightarrow A(n_0+1)\red{)}$
[/mm]
sofort, dass [mm] $A(n_0+1)$ [/mm] wahr sein muss.
2.) [mm] $A(n_0+1)$ [/mm] ist nun wahr (siehe 1.). Weil die Folgerung
[mm] $A(n_0+1) \Longrightarrow A((n_0+1)+1)=A(n_0+2)$ [/mm] gilt,
liefert
[mm] $A(n_0+1) \wedge \red{(}A(n_0+1) \Longrightarrow A(n_0+2)\red{)}$
[/mm]
sofort, dass [mm] $A(n_0+2)$ [/mm] wahr sein muss.
etc. pp.!
Daraus folgt dann, dass [mm] $A(n_0+k)$ [/mm] für alle $k [mm] \in \IN_0$ [/mm] wahr ist. Die Menge
[mm] $$\{n_0+k:\;\; k \in \IN_0\}$$
[/mm]
ist aber gerade
[mm] $$\{n \in \IN_0:\;\; n \ge n_0\}\,.$$
[/mm]
Also haben wir so [mm] $A(n)\,$ [/mm] für alle $n [mm] \ge n_0$ [/mm] bewiesen.
Ich habe übrigens hier (klick!) heute Nacht etwas dazu geschrieben!
(Was dabei vielleicht etwas verwirrend ist, oder unschön rüberkommt, ist,
dass dort nicht beschrieben wird, wie der Beweis zu $A [mm] \Longrightarrow [/mm] B$ eigentlich
abläuft: Man setzt voraus, dass [mm] $A\,$ [/mm] gilt, und zeigt dann, das dann auch [mm] $B\,$ [/mm] gelten
muss. Warum zeigt das, dass $A [mm] \Longrightarrow [/mm] B$ gilt? Nunja:
$A [mm] \Longrightarrow [/mm] B$ ist per Definitionem nichts anderes als [mm] $\neg [/mm] A [mm] \vee B\,.$ [/mm] Im Falle, dass [mm] $\neg [/mm] A$ gilt, ist
[mm] $\neg [/mm] A [mm] \vee [/mm] B$ sicher immer wahr. Nur im Falle [mm] $A\,$ [/mm] (d.h. [mm] $A\,$ [/mm] ist wahr) hat man also noch etwas
zu tun, um die Wahrheit von [mm] $(\neg [/mm] A [mm] \vee [/mm] B)$ dann zu erkennen - und das ist dann eben das
obige: Man hat in diesem Falle zu zeigen, dass [mm] $B\,$ [/mm] auch wahr ist!)
-----------------------------------------------------------------
-----------------------------------------------------------------
Und zu Deiner Frage mit dem "Ziel" bei Deinem Induktionsbeweis:
Du gehst im Induktionsschritt davon aus, dass die Ungleichung $ n! [mm] \le n^{n-1} [/mm] $
für ein $ [mm] n\, [/mm] $ gilt.
Du zeigst nun, dass die Folgerung $ n! [mm] \le n^{n-1} \Longrightarrow [/mm] (n+1)! [mm] \le (n+1)^{(n+1)-1} [/mm] $ bzw.
$ n! [mm] \le n^{n-1} \Longrightarrow [/mm] (n+1)! [mm] \le (n+1)^n [/mm] $
gilt (das ist das ZIEL, das man im Induktionsschritt hinbekommen will: die
Gültigkeit dieser Folgerung).
Und das beendet dann den Induktionsbeweis, sofern es gelingt, diese
Folgerung zu beweisen!
Denn Frage: Wie lauten denn bei Dir die Aussagen $ [mm] A(n)\,, [/mm] $ die zu beweisen sind?
Gruß,
Marcel
|
|
|
|
