Vollständige Induktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:46 Di 31.01.2006 | | Autor: | FlorianJ |
| Aufgabe | Zeigen Sie:
$ [mm] \vektor{n \\ k} \bruch{1}{n^{k}} \le \bruch{1}{k!} [/mm] $
(k,n N, k [mm] $\le$ [/mm] n) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo erstmal.
Bin neu hier und hoffe Hilfe zu finden  .
Dann schieß ich mal los.
Der Induktionsanfang stimmt für n=3 und k=2.
Daher sind wir beim Induktionsschritt:
zZ: [mm] \vektor{n+1 \\ k} \bruch{1}{(n+1)^{k}} \le \bruch{1}{k!} [/mm]
Genau genommen bin ich hier schon raus, aber ich forme mal ein wenig um und komme hier hin:
[mm] \bruch{(n+1)n!}{k!(n+1-k)! *(n+1)^{k}} \le \bruch{1}{k!}
[/mm]
[mm] \bruch{n!}{k!(n+1-k)! *(n+1)^{k-1}} \le \bruch{1}{k!}
[/mm]
tjoa, so sieht es aus und ich weiß nicht einmal ob ich auf dem richtigen Weg bin, also bitte ich mal um Hilfe :)
danke schonmal
|
|
| |
|
Hallo FlorianJ,
musst Du die Aufgabe unbedingt via vollst. Induktion fuehren ?
Wenn nein, dann formen wir doch mal um und schauen einfach mal scharf hin, ok ?
Also: Deine Ungl. umgestellt ergibt doch
[mm] {n\choose k}\cdot k!\:\:\leq\:\: n^k
[/mm]
Die rechte Seite ist die Anzahl der Abbildungen von einer k-elementigen Menge in
eine n-elementige Menge, oder ?
Die linke Seite: Wir waehlen aus n Elementen k aus und betrachten alle k! Moeglichkeiten, diese als die Bilder der k Elemente einer Menge der Kardinalitaet k zu
benutzen. Also links steht die Anzahl injektiver Abbildungen von einer k-elementigen in eine n-elementige Menge, und rechts die Anzahl aller Abbildungen von einer k-elem. Menge in eine n-elem. Menge (juhu, es gilt nach Vorauss. [mm] k\leq [/mm] n).
Das war's dann auch schon.
Klappt's auch via Induktion ? Gucken wir mal:
Den Anfang hast Du wohl schon, oder ? Der Anfang sollte n=k lauten.
Also zum Induktionsschritt: Gelte [mm] n\geq [/mm] k.
Zu zeigen: [mm] {n+1\choose k}\cdot k!\:\:\leq \:\: (n+1)^k
[/mm]
Linke Seite ist
[mm] ({\n\choose k}+{n\choose k-1})\cdot [/mm] k!
und das ist nach Vorauss.
[mm] \leq n^k [/mm] + [mm] k\cdot n^{k-1}
[/mm]
Rechte Seite ist gleich
[mm] \sum_{i=0}^k {k\choose i}\cdot n^i
[/mm]
und der letzte Summand davon ist [mm] 1\cdot n^k [/mm] und der vorletzte ist gleich
[mm] {k\choose 1}\cdot n^{k-1}=k\cdot n^{k-1}
[/mm]
womit also der Induktionsschritt fertig waere.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:13 Di 31.01.2006 | | Autor: | mathiash |
Hallo Florian, hallo alle,
meiner Ansicht nach passt dieser Artikel besser ins Forum Diskrete Mathematik als unter
Logik/Mengenlehre, deswegen habe ich ihn dorthin verschoben.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:18 Di 31.01.2006 | | Autor: | FlorianJ |
Vielen Dank, ich habs verstanden.
Da heißt es wohl weiter pauken und Daumen drücken um selbst auf solch eine Lösung zu kommen :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:23 Di 31.01.2006 | | Autor: | mathiash |
Hallo Florian,
... und wenn Du wirklich gut werden willst: Aufgaben rechnen, soviel Du kannst. Zur Kombinatorik zum Beispiel solche aus dem Buch von Lovasz ''Combinatorial Problems and Exercises'', zur Mengenlehre solche aus dem Buch ''Set Theory'' (oder so) von Jech.
Rechne auch ueber die Uni-Uebungsaufgaben hinaus solche aus Buechern, das bringt Dich dann voran, und erst so wirst Du merken, wozu Du wirklich in der Lage bist.
Viele Gruesse,
Mathias
|
|
|
|
