Beweise (2n über k) = ... < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:31 Mi 09.11.2005 | | Autor: | fvs |
Die Aufgabe lautet:
Beweisen Sie: [mm] \vektor{2n \\ n} [/mm] = [mm] \summe_{k=0}^{n} \vektor{n \\ k}².
[/mm]
Ich habe gar keine Idee, ich hoffe, dass mir jemand helfen kann.
Natürlich habe ich den Induktionsanfang bewiesen. .Ich habe dann angenommen, dass die Aussage auch für n+1 wahr ist, Wenn ich die rechte Seite "aufdrösel" erhalte ich [mm] 2^n+1. [/mm] Das bekomme ich allerdings nicht auf der linken Seite heraus.
Ich habe diese Frage noch in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:10 Do 10.11.2005 | | Autor: | Stefan |
Hallo!
Man hat jetzt zwei Möglichkeiten: Entweder man zieht eine fiese Induktion durch oder aber man löst die Aufgabe elegant. Ich entscheide mich für letzteres.
Betrachte die Menge [mm] $M:=\{x_1,\ldots,x_n,y_1,\ldots,y_n\}$ [/mm] mit $2n$ verschiedenen Elementen. Die $n$-elementigen Teilmengen dieser Klassen zerfallen in $n+1$ Klassen [mm] $A_i$ ($i=0,\ldots,n-1)$, [/mm] wobei in [mm] $A_i$ [/mm] diejenigen Teilmengen liegen, die $i$ der [mm] $x_j$'s [/mm] und $n-i$ der [mm] $y_j$'s [/mm] enthalten. Bekanntlich enthält [mm] $A_i$ [/mm] dann
${n [mm] \choose [/mm] i } [mm] \cdot [/mm] {n [mm] \choose [/mm] n-i} = {n [mm] \choose i}^2$
[/mm]
Elemente. Damit ergibt sich die Anzahl aller $n$-elementigen Teilmengen von $M$ als
[mm] $\sum\limits_{i=0}^n [/mm] {n [mm] \choose i}^2$ [/mm] .
Andererseits ist diese Anzahl aber bekanntlich gleich ${2n [mm] \choose [/mm] n}$.
Das war'S.
Liebe Grüße
Stefan
|
|
|
|
