Binomialkoeffizient < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Beweisen Sie die folgende Beziehung für Binomialkoeffizienten:
a) [mm] \summe_{k=0}^{n}(\vektor{n \\ k})^{2} [/mm] = [mm] \vektor{2n \\ n}, [/mm] n = 0,1,... |
Also für die erste Aufgabe habe ich zumindest eine Idee: Ich weiss, dass [mm] \vektor{n \\ k} [/mm] = [mm] \bruch{n}{n-k}*\vektor{n-1 \\ k}. [/mm]
Ich habs mir Induktion versucht und bisher ist das dabei herausgekommen:
IA: Sei n = 0, die Behauptung hält offensichtlich.
IV: [mm] \summe_{k=0}^{n}(\vektor{n \\ k})^{2} [/mm] = [mm] \vektor{2n \\ n}
[/mm]
IBeh.: [mm] \summe_{k=0}^{n+1}(\vektor{(n+1) \\ k})^{2} [/mm] = [mm] \vektor{2(n+1) \\ (n+1)}
[/mm]
IS: [mm] \summe_{k=0}^{n+1}(\vektor{(n+1) \\ k})^{2} [/mm] = [mm] \summe_{k=0}^{n+1}(\bruch{n+1}{n-k+1}*\vektor{n \\ k})
[/mm]
Hier finde ich zumindest schonmal meine Induktionsvoraussetzung irgendwie wieder, aber ich habs bisher nicht geschafft, die Voraussetzung einzusetzen, weil der Faktor [mm] \bruch{n+1}{n-k+1} [/mm] stört.
Es würde mir reichen, wenn mir wenigstens jemand sagt, ob ich schonmal den richtigen Weg eingeschlagen habe, oder ob meine Idee gar nicht zum Ziel führt bzw. mir jemand einen kleinen Tipp gibt, was ich sonst noch probieren könnte, damit ich selbst noch ein bisschen herumprobieren kann und vielleicht noch selbst auf die Lösung komme.
Vielen Dank
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:10 Fr 13.06.2008 | | Autor: | statler |
Mahlzeit! Und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Beweisen Sie die folgende Beziehung für
> Binomialkoeffizienten:
>
> a) [mm]\summe_{k=0}^{n}(\vektor{n \\ k})^{2}[/mm] = [mm]\vektor{2n \\ n},[/mm]
> n = 0,1,...
> Also für die erste Aufgabe habe ich zumindest eine Idee:
> Ich weiss, dass [mm]\vektor{n \\ k}[/mm] =
> [mm]\bruch{n}{n-k}*\vektor{n-1 \\ k}.[/mm]
> Ich habs mir Induktion versucht und bisher ist das dabei
> herausgekommen:
Ich will dich nicht davon abhalten, das mit vollst. Ind. zu versuchen. Ich würd's allerdings anders anpacken. Der rechte Binomialkoeffizient gibt an, wie viele Möglichkeiten es gibt, n-elementige Teilmengen aus einer 2n-elementigen Menge auszuwählen. So eine Teilmenge setzt sich zusammen aus einer k-elementigen Teilmenge der unteren Hälfte und einer (n-k)-elementigen Teilmenge der oberen Hälfte.
Jetzt breche ich mal ab und überlasse es dir, diesen Ansatz in einen Beweis zu verwandeln (oder auch nicht).
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:21 Fr 13.06.2008 | | Autor: | DerAntiPro |
Wow, auf die Idee bin ich gar nicht gekommen, hatte wohl zu sehr den Tunnelblick auf Induktion weil in der Aufgabe stand "für alle n N".
Den Beweis hab ich jetzt auch fertig augeschrieben, vielen Dank und liebe Grüße!
|
|
|
|
