matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikVollständige Induktion
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Diskrete Mathematik" - Vollständige Induktion
Vollständige Induktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

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



        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 14:09 Di 31.01.2006
Autor: mathiash

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

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

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

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]