Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Binomialidentität

Binomialidentität

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Binomialkoeffizient, kombinatorischer Beweis

Clemensum aktiv_icon

20:13 Uhr, 13.05.2012

Es ist rein kombinatorisch zu zeigen:

(\binom{n + 1}{k + 1}) = \sum_{m = k}^{n} (\binom{m}{k})

Ich habe schon maö eine sehr ähnliche Frage gestellt, jedoch ist es leider nicht mehr möglich diese zu behandeln, jetzt muss ich mich jedoch wegen Prüfungsvorbereitung wieder damit befassen.

So, bei meiner Lösungsidee kann ich mal folgendes sagen:
Die linke Seite ist einfach die Anzahl aller n+1 elementigen Teilmengen einer

k + 1

elementigen Menge. Die rechte Seite bildet "oder - Verknüpfungen", vereinigt also alle

k -

elementigen Teilmengen, wobei die Anzahl der Elemente in der Grundmenge jeweils um eins ansteigt und von k bis n geht. Ich vereinige also alle Mengen auf der rechten Seite von

m = k

bis

n .

Ich sehe aber leider überhaupt nicht, warum das zur Gleichheit führen soll.

Gelingt es vielleicht mit geeigneten Färbungen ? Ich kann es nicht machen, in dem ich z.B. ein beliebiges aber festes Element betrachte und dann die Fälle (a aus einer Teilmenge, a nicht aus einer Teilmenge) betrachte. Das ginge doch nur, wenn ich auf zwei Summanden aufspalte. Außerdem würde sich bei letzterer Methode auch die Elementanzahl in den Teilmengen verringern.

Kann mir jemand einen Tipp geben, wie ich weiter kommen könnte, wäre euch sehr dankbar!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

Aurel

02:27 Uhr, 14.05.2012

Von welchen Voraussetzungen darft du bei "rein kombinatorisch" ausgehen?

wenn du die Voraussetzung

(\begin{matrix} n + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k + 1 \end{matrix})

als gegeben annehmen darfst

- siehe: de.wikipedia.org/wiki/Binomialkoeffizient#Rechenregeln -

dann:

(\begin{matrix} n + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k + 1 \end{matrix})

mit

(\begin{matrix} n \\ k + 1 \end{matrix}) = ... ... ... .

. wegen Voraussetzung

(\begin{matrix} n - 1 \\ k \end{matrix}) + (\begin{matrix} n - 1 \\ k + 1 \end{matrix})

mit

(\begin{matrix} n - 1 \\ k + 1 \end{matrix}) = ... ... ... .

. wegen Voraussetzung

(\begin{matrix} n - 2 \\ k \end{matrix}) + (\begin{matrix} n - 2 \\ k + 1 \end{matrix})

mit

(\begin{matrix} n - 2 \\ k + 1 \end{matrix}) = ... ... ... .

. wegen Voraussetzung

(\begin{matrix} n - 3 \\ k \end{matrix}) + (\begin{matrix} n - 3 \\ k + 1 \end{matrix})

usw.

also:

(\begin{matrix} n + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n - 1 \\ k \end{matrix}) + (\begin{matrix} n - 2 \\ k \end{matrix}) + (\begin{matrix} n - 3 \\ k \end{matrix}) +

... .

+ (\begin{matrix} k + 1 \\ k + 1 \end{matrix}) = \sum_{m = k}^{n} (\begin{matrix} m \\ k \end{matrix})

weil

(\begin{matrix} k + 1 \\ k + 1 \end{matrix}) = (\begin{matrix} k \\ k \end{matrix}) = 1

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1002551

1002402

	Status: nicht eingeloggt	Noch nicht registriert?