Vandermondesche Identität per Induktion

16.10.2009, 00:07

Nerto

Vandermondesche Identität per Induktion

Ich soll beweißen ( per Induktion) das $\begin{eqnarray*} {m+n \choose k} = \sum \limits _{i =0}^k {m \choose i} * {n \choose k - i} \end{eqnarray*}$ gilt für alle $\begin{eqnarray*} m,n,k \in N \end{eqnarray*}$ .

Mein Gedanke war ich induziere über k.

IB: Klar
IS:
$\begin{eqnarray*} {m+n \choose k+ 1} = \frac{(n+m)(n+m-1)...(n+m-k)}{1*2*...*k*(k+1)} = (\sum \limits _{i = 0}^k {m \choose i} * {n \choose k - i}) \cdot \frac{n+m-k}{k+1} \end{eqnarray*}$
jetzt hab ich ausgenutzt das $\begin{eqnarray*} {n \choose k - (k+1)} = 0 \end{eqnarray*}$ ist
= ( $\begin{eqnarray*} \sum \limits _{i =1}^{k+1} {m \choose i} * {n \choose k - i}) \cdot \frac{n+m-k}{k+1} \end{eqnarray*}$

aber jetzt komm ich einfach nicht weiter ...

16.10.2009, 11:38

Schmonk

Auf diesen Beitrag antworten »

RE: Vandermondesche Identität per Induktion
Hallo!

Zitat:

Original von Nerto
jetzt hab ich ausgenutzt das $\begin{eqnarray*} {n \choose k - (k+1)} = 0 \end{eqnarray*}$ ist

Sagt wer?

$\begin{eqnarray*} {n \choose k - (k+1)} = {n \choose -1}=\mbox{Krautsalat} \end{eqnarray*}$
Nur für n=0 wäre deine Aussage richtig. Zumindest irgendwie.

Edit: Und den Beweis von Vandermonde kenne ich nur mit Mitteln der Mengenlehre bzw. Kombinatorik. Induktion sollte ziemlich schwer werden, zumal du genau genommen eine dreifach geschachtelte Induktion über m, n und k ausführen musst.

Edit 2 : Und weil ich gerade nach AUsreden suche, um nicht an meiner Diplomarbeit weiterzuarbeiten gebe ich dir einen Tipp zum Anfang:

Betrachte zwei disjunkte Mengen $\begin{eqnarray*} N \end{eqnarray*}$ und $\begin{eqnarray*} M \end{eqnarray*}$ mit $\begin{eqnarray*} \vert N\vert=n \end{eqnarray*}$ und $\begin{eqnarray*} \vert M\vert=m \end{eqnarray*}$ .
Interessant für dich sind jetzt die Mengen
$\begin{eqnarray*} \mathcal{P}_i:=\left\{P\subseteq\left(N\cup M\right): \vert P\vert=k \mbox{~~und~~} \vert P\cap N\vert =i\right\} \end{eqnarray*}$

Denk hier erstmal drüber nach, sauber aufgeschrieben ist der Beweis dann etwa eine halbe Seite lang.

Grüße

16.10.2009, 14:47

Nerto

Auf diesen Beitrag antworten »

$\begin{eqnarray*} {n \choose k - (k+1)} = {n \choose -1}=\mbox{Krautsalat} \end{eqnarray*}$
steht halt so Forster Analysis beim Beweis von binomischen Lehrsatz und beim allgemeiner des Binomialkoeffizient - Ich weiß das Lehrbücher nicht immer rest haben-.

Ich muss den Beweiß halt mit Induktion machen und bei den Mengen seh ich leider nicht wie das mit Induktion gehen soll.

16.10.2009, 15:15

Schmonk

Auf diesen Beitrag antworten »

hmm, interessant, ich habe es damals so gelernt, dass die untere Zahl im Binomialkoeffizienten immer eine natürliche Zahl (Null eingeschlossen) sein soll, sonst ist das Ganze nicht definiert.

Auf der von dir verlinkten Seite wird weiter oben auch eine anschauliche Beweisidee für dein Problem geliefert. Die läuft genau in die Richtung, welche ich vorschlagen wollte.

Genau genommen braucht man dabei auch ein bischen Induktion. Augenzwinkern

Neue Frage »

Antworten »

Vandermondesche Identität per Induktion

Verwandte Themen