Induktionsbeweis von n! < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:21 Do 22.01.2009 | | Autor: | ggg |
Hallo ,
bei mir hinkt es seit einger Zeit an dem Beweis von n! durch Induktion.
Ich schreibe den Satz auf und das was ich vom Beweis verstanden habe. Ich bin neu hier und würde auch den wirklichen Beweis von Otto Forster aus aus Analysis 1 hinschreiben und dann meines wie ich das verstanden habe, aber ich bin mir nicht sicher, ob das erlaubt sei
Definition: [mm] n!=\produkt_{k=1}^{n} [/mm] k =1*2*n
[mm] (\produkt_{k=m}^{n} a_k)*a_n+1 [/mm] := [mm] \produkt_{k=m}^{n+1} a_n+1
[/mm]
Satz: Die Anzahl aller möglichen Anordnungen einer n-elemetigen Menge { [mm] A_{1}, A_{2}, \cdots, A_{n} [/mm] } ist gleich n!
Beweis:
Induktions_Anfang n=1.
Eine Anordung besteht aus einen Element und deshalb wäre folglich 1! gleich 1
Induktion_Schritt: Aus n folgt n+1, sodass aus [mm] \produkt_{k=1}^{n} a_k [/mm] dann [mm] (\produkt_{k=1}^{n} a_k)*a_n+1 [/mm] wird.
Auf Grund dessen ist dann k=1,2,..n,n+1, sodass das neue k als Element die Menge mit neuen Elementen füllt { [mm] A_{1}, A_{2}, \cdots, A_{n}, A_{n+1} [/mm] }.
Weil [mm] (\produkt_{k=m}^{n} a_k)*a_n+1 [/mm] definitionsgemäß [mm] \produkt_{k=m}^{n+1} a_n+1 [/mm] ist, und das ist wiederum das gleiche wie n!*(n+1)=(n+1)!ist,ist somit der Satz bewiesen [mm] \Box
[/mm]
Ist der Beweis so richtig wie das hingeschrieben habe
Apropos, Mir ist schon bekannt das ich damit die unendliche Anzahl von Permutation beweise
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo ggg,
also ob das so wie du argumentierst ausreicht weiß ich nicht.
Ich glaub bei diesem Problem hilft es, ein wenig weniger schreibfaul zu sein.
Du hast du Menge [mm] A=\{A_1,...A_n\} [/mm] und nach Voraussetzung gibt es n! verschiedene n-Tupel mit Elementen aus A. Jetzt nehmen wir uns ein [mm] A_{n+1} [/mm] -tes Element hinzu und fragen uns, an welche Stelle dieses [mm] A_{n+1} [/mm] überall hinkann.
Offensichtlich kann bei jeder der n! Permutationen das [mm] A_{n+1}-te [/mm] Element entweder an die 0-te, 1-te, 2-te,... oder n-te Stelle. Jedesmal entsteht dabei eine andere Permutation.
Damit hat gezeigt, dass es (n+1)*n! Permutaionen für diesen Fall gibt (weil ja auch an die "0-te" Stelle das neue Element hin kann).
lg Kai
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:38 Sa 24.01.2009 | | Autor: | ggg |
Wie ich entnehmen kann, ist meine Argumentation zum Beweis Lückenhaft und das sehe ich auch ein aber an welche Stelle meines Versuches zum erklären des Beweis würde man skeptisch werden ob es der Wahrheit entsprecht. Oder reicht deine Argumentation vollkommen aus. Im Buch ist der Beweis teilweise kompliziert erklärt worden, sodass ich kaum vorstellen kann, dass der Beweis tatsächlich so einfach ist wie du es mir gezeig hast.
Ich werde mal versuchen deine Argumentation mit meiner zu mischen vielleicht wird der Beweis so dann exakter und einfacher.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:35 Sa 24.01.2009 | | Autor: | Sigrid |
Hallo ggg,
Kais Beweis ist richtig und ich denke auch ausreichend. Mach Dir klar, dass bei einer Reihe von n Elementen n+1 Stellen gibt, ein neues Element einzufügen.
Du hast geschrieben:
Definition: $ [mm] n!=\produkt_{k=1}^{n} [/mm] $ k =1*2*n
$ [mm] (\produkt_{k=m}^{n} a_k)\cdot{}a_n+1 [/mm] $ := $ [mm] \produkt_{k=m}^{n+1} a_n+1 [/mm] $
Vermutlich meintest Du
$ [mm] (\produkt_{k=m}^{n} a_k)\cdot{}a_{n+1} [/mm] $ = $ [mm] \produkt_{k=m}^{n+1} a_k [/mm] $
Was für eine Folge [mm] a_k [/mm] willst Du denn hier nehmen? Du brauchst doch nur:
$ [mm] \produkt_{k=1}^{n} [/mm] k [mm] \cdot [/mm] (n+1) = [mm] \produkt_{k=1}^{n+1} [/mm] k = (n+1)! $
Gruß
Sigrid
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:48 Mo 26.01.2009 | | Autor: | ggg |
Hallo, Danke für eure schnelle Antworten!
Ich habe mir einen neuen Anlauf des Beweises mit eure Hilfe Versucht, weil ich denke wenn ich es schaffe mir selbst den beweis mit eigenen Worten zu erklären, habe ich das wirklich ohne zweifeln kapiert.
Beweis:
Induktion_Anfang n=1.
Eine Anordnung besteht aus einen Element und deshalb wäre folglich 1! gleich 1
Induktionsschritt aus n folgt n+1. Man hat eine Menge [mm] A_{n}= [/mm] { [mm] A_{1}, A_{2}, [/mm] ..., [mm] A_{n} [/mm] } mit n verschiedene Möglichkeiten einer Permutation. Da aber das Glied der menge um ein neues Element erweitert wird, wodurch dann n+1 Plätze zu Verfügung stehen, kann dann offensichtlich an jeder beliebiger Stelle der Permutation das Element gesetzt werden, wobei immer eine neue Permutation ensteht. Die neue Menge sei dann [mm] A_{n+1}= [/mm] { [mm] A_{1}, A_{2}, [/mm] ..., [mm] A_{n+1} [/mm] } wobei dann k=1,2,3, ...,n+1 ist und dies ist nichts anderes als (n+1)!*n!=(n+1)! [mm] \Box
[/mm]
Bitte könnt ihr mir sagen wo was falsch ist oder unschlüssig, Das ist mir sehr wichtig das ich den Beweis auch richtig aufgestellt habe. Also keine Scheu vor Kritik
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:18 Di 27.01.2009 | | Autor: | leduart |
Hallo
>
> Beweis:
> Induktion_Anfang n=1.
>
> Eine Anordnung besteht aus einen Element und deshalb wäre
> folglich 1! gleich 1
>
> Induktionsschritt aus n folgt n+1. Man hat eine Menge
> [mm]A_{n}=[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{ [mm]A_{1}, A_{2},[/mm] ..., [mm]A_{n}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} mit n verschiedene
> Möglichkeiten einer Permutation.
Richtig waere es gibt dazu n! verschiedene Permutationen.
> Da aber das Glied der
> menge um ein neues Element erweitert wird, wodurch dann n+1
> Plätze zu Verfügung stehen, kann dann offensichtlich an
> jeder beliebiger Stelle der Permutation das Element gesetzt
hier sprichtst du von "der" Permutation, du hast aber n! Permutationen. es muss also weiter gehen mit in jeder kann man das neue A an n+1 Paetze setzen!
> werden, wobei immer eine neue Permutation ensteht. Die neue
> Menge sei dann [mm]A_{n+1}=[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{ [mm]A_{1}, A_{2},[/mm] ..., [mm]A_{n+1}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
Das gehoert an den Anfang, oder ist so klar, dass man es nicht sagen muss>
> wobei dann k=1,2,3, ...,n+1 ist und dies ist nichts anderes
den satz versteh ich nicht, wo spielt das k ne Rolle vorher?
> als (n+1)!*n!=(n+1)! [mm]\Box[/mm]
und was heisst "dies ist nichts anderes?
irgendwo muss doch stehen : daraus folgt dass die anzahl der Anordnungen ..... ist.
> Bitte könnt ihr mir sagen wo was falsch ist oder
> unschlüssig, Das ist mir sehr wichtig das ich den Beweis
> auch richtig aufgestellt habe. Also keine Scheu vor Kritik
Die Scheu war weg.
Du musst deutlicher gliedern Vors. richtig fuer n dann zufuegen des (n+1)ten elements und das deutliche Argument warum es jetzt n+1 mal so viele moeglichkeiten sind wie vorher!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:08 Mo 02.03.2009 | | Autor: | ggg |
Vielleicht kommt das etwas zu spät aber trotzdem danke ich euch sehr, Ich habe auch endlich die Beweisstruktur erkannt und das tolle daran ist das ich jetzt ein viel besseren Durchblick bei den Beweisen gewonnen habe.
|
|
|
|
