www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Analysis-Induktion" - vollständige Induktion
vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 01:10 Sa 27.04.2013
Autor: reverend

Hallo Diahara, [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]

> 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

Bezug
                
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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. :-)

Bezug
                
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
vollständige Induktion: I.A. mit n=1
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
vollständige Induktion: Rückfrage
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de