Weisen nach n über k gilt? < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Weisen Sie nach, dass [mm] \pmat{ n+1 \\ k + 1 }=\pmat{ n \\ k }+\pmat{ n \\ k+1 } [/mm] gilt. |
Hallo liebe Mathefreunde,
bei dieser Aufgabe bin ich ein bisschen stutzig. Ich denke mal das ganze soll per Vollständige Induktion nachgewiesen werden.
Aber um ehrlich zu sein versteh ich nicht einmal den Ausdruck [mm] \vektor{n+1 \\ k+1}.
[/mm]
Dachte eigentlich früher immer, dass ist die Schreibweise für Vektoren, aber
als ich in meinem Heft nachgeschaut habe, habe ich rausgefunden, dass
[mm] \vektor{n \\ k}=\bruch{n!}{k!*(n-k)!} [/mm] bedeutet.
?? Wie kommt man denn da drauf und was bedeutet das für das Beispiel in der Aufgabe?
Gruß,
Philipp
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:37 Mi 23.11.2011 | | Autor: | Stoecki |
[mm] \vektor{n \\ k} [/mm] ist die anzahl von möglichkeiten k elemente aus einer menge von n elementen auszuwählen. (gesprochen n über k)
wenn man es nicht kennt, dann ist es sicherlich so, dass man zuerst an vektoren denkt.
es gilt, wie du schon geschrieben hast: [mm] \vektor{n \\ k}=\bruch{n!}{k!\cdot{}(n-k)!}
[/mm]
dabei ist n!:= n*(n-1)*(n-2)*...*3*2
für die aufgabe bedeutet das, dass du da eine, wenn ich mich richtig an mein erstes semester erinnere, hässliche induktion durchführen musst.
gruß bernhard
|
|
|
| |
|
> dabei ist n!:= n*(n-1)*(n-2)*...*3*2
Ok, jetzt habe ich es verstanden. :D Danke!
Für mein Beispiel würde das bedeuten:
[mm] \vektor{n+1 \\ k+1}=\bruch{n+1!}{k+1!\cdot{}(n-k+1!)}
[/mm]
Dementsprechend müsste der Ind.anfang so sein:
n=1; [mm] \vektor{2 \\ 2}=\bruch{2}{2(2-2)!}
[/mm]
Setze ich für k auch eins ein, wenn n=1?
Da kommt eine 0 unter dem Bruch raus, kann also irgendwie nicht sein...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:27 Mi 23.11.2011 | | Autor: | fred97 |
> > dabei ist n!:= n*(n-1)*(n-2)*...*3*2
>
> Ok, jetzt habe ich es verstanden. :D Danke!
>
> Für mein Beispiel würde das bedeuten:
>
> [mm]\vektor{n+1 \\ k+1}=\bruch{n+1!}{k+1!\cdot{}(n-k+1!)}[/mm]
Klammern nicht vergessen:
[mm]\vektor{n+1 \\ k+1}=\bruch{n+1!}{(k+1)!\cdot{}(n-k+1!)}[/mm]
>
>
> Dementsprechend müsste der Ind.anfang so sein:
>
> n=1; [mm]\vektor{2 \\ 2}=\bruch{2}{2(2-2)!}[/mm]
Das ist kein Induktionsanfang. Da Du eine Gl. zeigen sollst, sollte auch eine Gleichung dastehen.
Dass Du keine Induktion machen mußt habe ich Dir hier geschrieben:
https://matheraum.de/read?i=841749
>
> Setze ich für k auch eins ein, wenn n=1?
>
> Da kommt eine 0 unter dem Bruch raus, kann also irgendwie
> nicht sein...
Es ist 0!=1
FRED
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:15 Mi 23.11.2011 | | Autor: | fred97 |
Ich kann Stoeckli nicht zustimmen. Induktion ist nicht erforderlich.
Mit $ [mm] \vektor{n \\ k}=\bruch{n!}{k!\cdot{}(n-k)!} [/mm] $ rechne einfach die linke und die rechte Seite der zu beweisenden Gleichung aus und schau nach ob sie übereinstimmen.
Wenn nicht, hast Du Dich verrechnet.
FRED
|
|
|
| |
|
Ahh ok, sehr gute Idee. ich probiere es gleich einmal aus, kann aber eine Weile bei mir dauern...
|
|
|
| |
|
Beim ausrechnen, komme ich wieder auf meine Grenzen.
Gelten die normalen Rechengesetze?
Ich habe nun:
[mm] \bruch{(n+1)!}{(k+1)!(n+1-k+1)!}=\bruch{n!}{k!(n-k)!}+\bruch{n!}{(k+1)!(n-k+1)!}
[/mm]
zusammenfassen kann ich noch bis:
[mm] \bruch{(n+1)!}{(k+1)!(n-k+2)!}=\bruch{n!}{k!(n-k)!}+\bruch{n!}{(k+1)!(n-k+1)!}
[/mm]
aber was mach ich mit der rechten Seite? Ich kann ja nicht ausmultiplizieren oder so..
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:56 Mi 23.11.2011 | | Autor: | fred97 |
> Beim ausrechnen, komme ich wieder auf meine Grenzen.
> Gelten die normalen Rechengesetze?
>
> Ich habe nun:
>
> [mm]\bruch{(n+1)!}{(k+1)!(n+1-k+1)!}=\bruch{n!}{k!(n-k)!}+\bruch{n!}{(k+1)!(n-k+1)!}[/mm]
>
> zusammenfassen kann ich noch bis:
>
> [mm]\bruch{(n+1)!}{(k+1)!(n-k+2)!}=\bruch{n!}{k!(n-k)!}+\bruch{n!}{(k+1)!(n-k+1)!}[/mm]
>
> aber was mach ich mit der rechten Seite?
Addiere die beiden Brüche
FRED
> Ich kann ja nicht
> ausmultiplizieren oder so..
|
|
|
| |
|
> [mm]\bruch{(n+1)!}{(k+1)!(n-k+2)!}=\bruch{n!}{k!(n-k)!}+\bruch{n!}{(k+1)!(n-k+1)!}[/mm]
> >
> > aber was mach ich mit der rechten Seite?
>
> Addiere die beiden Brüche
Ja das habe ich mir auch überlegt, aber ich kann ja den Nenner nicht einfach um 1 erweitern mit einer Fakultät? oder einfach so:
[mm] \bruch{(n+1)!}{(k+1)!(n-k+2)!}=\bruch{n!*((k+1)!(n-k+1)!}{(k!(n-k)!)((k+1)!(n-k+1)!)}+\bruch{(n!)(k!(n-k)!)}{(k!(n-k)!)((k+1)!(n-k+1)!)}
[/mm]
und das führt zu:
[mm] \bruch{(n+1)!}{(k+1)!(n-k+2)!}=\bruch{(n!)(k+1)!(n-k+1)!)+(n!)(k!(n-k)!)}{(k!(n-k)!)((k+1)!(n-k+1)!)}
[/mm]
aber immernoch das gleiche Problem: wie mach ich weiter? Ich kann Fakultäten ja nicht addieren, multiplizieren etc...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:21 Mi 23.11.2011 | | Autor: | leduart |
Hallo
was fehlt denn bei k!*(n-k)! um auf (k+1)!*(n-1-k)! zu kommen?
dein HN ist zwar nicht falsch, aber so, wie wenn du HN von 37*38 und 74*76 als 37*38*74*76 rechnen würdest!
also such den kleinst mögichen HN
Wenn dus nicht siehst machs mal für n=4, k=2
gruss leduart
|
|
|
| |
|
ja das Problem ist nach wie vor das Zusammenfassen mit Fakultät.
wenn ich das mit n=4, k=2 mache ist das kein Problem, da ich 2!2! ohne Probleme im Kopf zusammenrechnen kann.
kushkush hat das ganz schön gemacht, aber ich verstehe absolut nicht die einzelnen Schritte darunter.
Wir haben Fakultät in der Schule nicht gehabt und in der Uni wird auf einmal damit gerechnet, gibt es da vllt eigene Rechengesetze wie für Log etc?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:05 Mi 23.11.2011 | | Autor: | leduart |
Hallo
k!=1*2*3*...*k
(k+1)!=1*2*3*....*k*(k+1)=k!*(k+1)
entsprechend:
(n-k)!=(n-1-k)!*(n-k)
das hat wenig mit schule zu tun, notfalls schreibt man sich das halt mit pünktchen hin!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:42 Mi 23.11.2011 | | Autor: | kushkush |
Hallo,
[mm] $$\vektor{n\\k} [/mm] + [mm] \vektor{n\\ k+1} [/mm] = [mm] \frac{n!}{(n-k)!k!} + \frac{n!}{(n-k-1)!(k+1)!} [/mm] = [mm] \frac{n!((n-k)!k!+(n-k-1)!(k+1)!)}{(n-k)!k!(n-k-1)!(k+1)!} [/mm] = [mm] \frac{n!((n-k)+(k+1))}{(n-k)!(k+1)!} [/mm] = [mm] \frac{(n+1)!}{(n+1-(k+1))!(k+1)!} [/mm] = [mm] \vektor{n+1\\ k+1}$$
[/mm]
das kannst du jetzt benutzen um:
[mm] $$\sum_{q=0}^{k} \vektor{n-1+q\\ n-1 } [/mm] = [mm] \vektor{n+k\\ k} [/mm] $$
mit Induktion zu zeigen.
Gruss
kushkush
|
|
|
| |
|
WOW vielen Dank, aber wie kommst du/fasst du zusammen vom 2.Gleichheitszeichen zum 3. Gleichheitszeichen?
|
|
|
| |
|
hmm ok, gleichnamig machen ist kein Problem, aber nicht mit Fakultät etc..
müsste es denn nicht am ende [mm] \vektor{n+1\\ k-1}
[/mm]
denn es heißt ja:
[mm] \bruch{n!}{(n-k-1)!(k+1)!} [/mm] und du hast hier ein
+
dementsprechend müsste es ja am ende k-1 heißen laut dieser Form.
Wie auch immer, das ist das geringste Problem, das Problem ist das Zusammenfassen :D
wie kommst du bspw. von n!((n-k)+k) zu (n+1)! ??
Ahh und ähm wieso denn mit Vollständiger Induktion, kann es doch so wie Fred gesagt hat machen :
[mm] \pmat{ n+1 \\ k + 1 }=\pmat{ n \\ k }+\pmat{ n \\ k+1 }
[/mm]
beide Seiten ausrechnen und wenn links und rechts das Gleiche rauskommt, dann ist die Sache bewiesen, oder? :D
|
|
|
| |
|
Hallo,
> wie auf n!((n-k)+k) zu (n+1)!
Das war ein Fehler.
$$ [mm] \vektor{n\\k} [/mm] + [mm] \vektor{n\\ k+1} [/mm] = [mm] \frac{n!}{(n-k)!k!} [/mm] + [mm] \frac{n!}{(n-k-1)!(k+1)!} [/mm] = [mm] \frac{n!((n-k)!k!+(n-k-1)!(k+1)!)}{(n-k)!k!(n-k-1)!(k+1)!} [/mm] = [mm] \frac{n!((n-k)+(k+1))}{(n-k)!(k+1)!} [/mm] = [mm] \frac{(n+1)!}{(n+1-(k+1))!(k+1)!} [/mm] = [mm] \vektor{n+1\\ k+1} [/mm] $$
Von der 1.ten zur 2.ten Gleichung in die Definition einsetzen. , von der 2.ten zur 3ten Gleichung: gleichnamig machen und n! ausklammern im Zähler, von der 3ten zur 4ten Gleichung: Aus der Summe im Zähler k!(n-k-1)! kürzen, 456 wieder in Definition einsetzen.
> Ahh und ähm wieso denn mit Vollständiger Induktion
Das ist keine vollständige Induktion.
Gruss
kushkush
|
|
|
| |
|
Ok, danke. Ich zerbrech mir mal den Kopf daran.
>
> Das ist keine vollständige Induktion.
>
Steht ja in der Aufgabe nicht drin, dass man das per vollst. Induktion machen muss, ich denke so ist das ja auch bewiesen.
|
|
|
|
![[]](/images/popup.gif){kind=small}
gleichnamig machen