Identität von Binomialkoeffizienten: Beweis für (2n tief n) = Summe (n über k)^2

Question

Zeige:

\( \sum \limits_{k=0}^{n}\left(\begin{array}{l}{n} \\ {k}\end{array}\right)^{2}=\left(\begin{array}{l}{2 n} \\ {n}\end{array}\right) \)

Geht das auch über Induktion? Alle meine Beweisversuche haben leider ins Leere geführt.

Answer 1

Es ist einfacher, wenn du hier kombinatorisch argumentierst.

Der Binomialkoeffizient ( p tief q) ist nach Definition die Anzahl der q-elementigen Teilmengen einer p-elementigen Mengen.

Rechte Seite der Behauptung:

(2n tief n) ist die Zahl der n-elementigen Teilmengen eine Menge mit 2n Elementen.

Beweis:

Teile nun deine 2n Elemente der Grundmenge in 2 Gruppen mit n Elementen auf.

Nun kannst du n-elementige Mengen aus der Grundmenge zusammenstellen aus:

k Elementen aus der ersten Gruppe und n-k Elementen aus der zweiten Gruppe. (k von 0 bis n)

Also Gesamtzahl der Teilmengen mit n Elementen aus Grundmenge Σ (n tief k) * (n tief (n-k)) summiert von k=0 bis n

Da in der zweiten Gruppe gilt: Wenn n-k Elemente genommen werden, bleiben k Elemente übrig, gilt:

(n tief (n-k)) = (n tief k).

Es folgt für die Gesamtzahl der Teilmengen mit n Elementen aus Grundmenge

Σ (n tief k) * (n tief (n-k)) summiert von k=0 bis n

= Σ (n tief k) * (n tief k) summiert von k=0 bis n

= Σ (n tief k)^2

Linke Seite der Behauptung. qed. Hier endet der kombinatorische Beweis deiner Formel.

Du kannst auch mit vollständiger Induktion arbeiten. Allerdings wäre mir die Rechnerei zu aufwändig und du lernst dabei nicht viel über die Bedeutung der Binomialkoeffizienten.