Vandermonde-Identität beweisen. Induktion?

Question

Hi, ich versuche gerade die folgende Aufgabe zu lösen. Weil mein Anhang sonst zu groß geworden wäre, habe ein Bild mit der Induktionsbehauptung und dem Induktionsanfang weggelassen. Der I.A. stimmt allerdings (das habe ich ausprobiert) und die Behauptung entspricht der I.V. die ich im unteren Bild nochmal umgeformt habe.

Mein Problem ist allerdings, dass ich nicht genau weiß, wie ich hier nun genau weitermachen soll, da die Induktionsvariable k hier Teil der Summe ist. Zur erklärung meines Anatzes (letzte Zeile): Ich habe schon versucht, durch Erweitern des Bruches wieder auf die Induktionsvoraussetzung zu kommen, aber das bringt mich durch die Fakultäten auch nicht weiter.

Habt ihr vielleicht eine Idee, wie ich weitermachen sollte? Oder habe ich womöglich jetzt schon einen Fehler gemacht?

Bin dankbar für jede Hilfe.

LG

Comments

Aloha :)

Das ist die sog. "Vandermonde-Identität". Den Beweis hier aufzuschreiben ist etwas fummelig. Im Netz solltest du unter dem o.g. Stichwort fündig werden.

---

Wenn einfach nur der Beweis verlangt sein sollte (nicht zwingend induktiv): Es geht auch kombinatorisch.

https://www.mathelounge.de/663761/kombinatorischer-beweis-fur-eine-gleichung#a663772

---

Guter Link, den man unbedingt anschauen sollten. Das ist aber nicht unbedingt Duplikat, weil dort ein kombinatorischer Beweis verlangt war. Hier steht in der Überschrift "Induktion."

Gegenseitige Verlinkung ist hier besser als gleich eine Verschmelzung.

---

Vom Duplikat:

Titel: Vandermondsche Identität vollständige Induktion

Stichworte: induktion,vollständige-induktion,identität

Aufgabe:

Beweise die Vandermondsche Identität mit der vollständigen Induktion.

$$  \sum \limits_{i=0}^{k} \begin{pmatrix} m\\i \end{pmatrix} \begin{pmatrix} n\\k-i \end{pmatrix} = \begin{pmatrix} m + n\\k \end{pmatrix} $$

Problem/Ansatz:

Ich habe bereits versucht, nach m zu induzieren, komme jedoch nach der Indexverschiebung nicht mehr weiter.

$$\sum \limits_{i=0}^{k+1} \begin{pmatrix} m\\i \end{pmatrix} \begin{pmatrix} n\\k+1-i \end{pmatrix} = \begin{pmatrix} m\\k+1 \end{pmatrix} + \sum \limits_{i=0}^{k} \begin{pmatrix} m\\i \end{pmatrix} \begin{pmatrix} n\\k+1-i \end{pmatrix}$$

Nach n zu induzieren schien mir dann leichter, aber auch dort kam ich nicht wirklich voran.

$$\sum \limits_{i=0}^{k} \begin{pmatrix} m\\i \end{pmatrix} \begin{pmatrix} n+1\\k-i \end{pmatrix} = \sum \limits_{i=1}^{k-1} \begin{pmatrix} m\\i \end{pmatrix} \bigg[\begin{pmatrix} n\\k-i \end{pmatrix} \begin{pmatrix} n\\k-i-1 \end{pmatrix}\bigg] + \begin{pmatrix} m\\k \end{pmatrix} + \begin{pmatrix} n+1\\k \end{pmatrix}$$

Da bin ich mir dann auch nicht sicher, ob ich den letzten Summanden richtig aus dem Summenzeichen rausgeholt habe, da ja dort eigentlich \begin{pmatrix} n\\-1 \end{pmatrix} stehen würde, das aber ja definitiv nicht sein kann.

---

Anscheinend hat Eichhörnchen vor einem Jahr die gleiche Frage gehabt. Unten nun die damaligen Antworten, die du bereits kommentiert hast, weil noch etwas unklar war.

Ich sehe auch nicht, welche Einschränkungen / Voraussetzungen bei k, n und m von Eichörnchen vorgegeben waren. D.h. da könnte ein Teil der Voraussetzungen fehlen. Besser vielleicht "Vandermonde-Identität" googeln. Buchstaben kann man ja umbenennen.

Answer 1

Benutze doch die (bekannte?) Formel

$$\begin{pmatrix} a+1\\b \end{pmatrix}=\begin{pmatrix} a\\b-1 \end{pmatrix}+\begin{pmatrix} a\\b \end{pmatrix}$$

oder beweise sie zunächst durch dein Umschreiben auf die Fakultäten.

Induktion über n könnte dann so aussehen:

$$\sum \limits_{l=0}^{n+1}\begin{pmatrix} n+1\\l \end{pmatrix}*\begin{pmatrix} m\\k-l \end{pmatrix}$$

und das müsste man unter Verwendung der Ind.vor. umformen zu

$$ \begin{pmatrix} n+1+m\\k \end{pmatrix} $$

Zuerst mal den ersten und den letzten Summanden extra schreiben

$$=\begin{pmatrix} n+1\\0 \end{pmatrix}*\begin{pmatrix} m\\k \end{pmatrix}+\sum \limits_{l=1}^{n}\begin{pmatrix} n+1\\l \end{pmatrix}*\begin{pmatrix} m\\k-l \end{pmatrix}+\begin{pmatrix} n+1\\n+1 \end{pmatrix}*\begin{pmatrix} m\\k-n-1 \end{pmatrix}$$

Jetzt die besagte Formel anwenden und die extra geschriebenen vereinfachen

$$=\begin{pmatrix} m\\k \end{pmatrix}+\sum \limits_{l=1}^{n}(\begin{pmatrix} n\\l-1 \end{pmatrix}+\begin{pmatrix} n\\l \end{pmatrix})*\begin{pmatrix} m\\k-l \end{pmatrix}+\begin{pmatrix} m\\k-n-1 \end{pmatrix}$$

In der Summe die Klammer auflösen und zwei Summen draus machen

$$=\begin{pmatrix} m\\k \end{pmatrix}+\sum \limits_{l=1}^{n}\begin{pmatrix} n\\l-1 \end{pmatrix}*\begin{pmatrix} m\\k-l \end{pmatrix}+\sum \limits_{l=1}^{n}\begin{pmatrix} n\\l \end{pmatrix}*\begin{pmatrix} m\\k-l \end{pmatrix}+\begin{pmatrix} m\\k-n-1 \end{pmatrix}$$

Der erste Binomialkoeffizient ist genau der 0-te Summand der 2. Summe, also

hat man schon mal

$$=\sum \limits_{l=1}^{n}\begin{pmatrix} n\\l-1 \end{pmatrix}*\begin{pmatrix} m\\k-l \end{pmatrix}+\sum \limits_{l=0}^{n}\begin{pmatrix} n\\l \end{pmatrix}*\begin{pmatrix} m\\k-l \end{pmatrix}+\begin{pmatrix} m\\k-n-1 \end{pmatrix}$$

und man kann für die 2. Summe die Ind.vor. einsetzen

$$=\sum \limits_{l=1}^{n}\begin{pmatrix} n\\l-1 \end{pmatrix}*\begin{pmatrix} m\\k-l \end{pmatrix}+\begin{pmatrix} n+m\\k \end{pmatrix}+\begin{pmatrix} m\\k-n-1 \end{pmatrix}$$

In der verbleibenden Summe den Index verschieben gibt

$$=\sum \limits_{l=0}^{n-1}\begin{pmatrix} n\\l \end{pmatrix}*\begin{pmatrix} m\\k-l-1 \end{pmatrix}+\begin{pmatrix} n+m\\k \end{pmatrix}+\begin{pmatrix} m\\k-n-1 \end{pmatrix}$$

Dann ist der letzte Binomialkoeffizient genau der n-te Summand dieser Summe, also gibt es

$$=\sum \limits_{l=0}^{n}\begin{pmatrix} n\\l \end{pmatrix}*\begin{pmatrix} m\\k-l-1 \end{pmatrix}+\begin{pmatrix} n+m\\k \end{pmatrix}$$

Das ist genau die Formel aus Indvoraussetzung für k-1an Stelle von k.

Also kann man das Ergebnis  einsetzen und hat

$$=\begin{pmatrix} n+m\\k-1 \end{pmatrix}+\begin{pmatrix} n+m\\k \end{pmatrix}$$

Und mit der eingangs zitierten Formel ergibt sich - wie gewünscht -

$$ \begin{pmatrix} n+1+m\\k \end{pmatrix} $$

Comments

vielen vielen Dank:)!

---

Hi, sorry, dass ich dich nochmal störe, aber ist es eigentlich generell so, dass ich die variable für die obergrenze vertauschen darf, so wie du es hier mit m und k gemacht hast? :)

---

Welchen Schritt meinst du denn ?

---

Ich meine das eigentlich generell. Du hast ja über n indiziert und ich habe es die ganze Zeit über k versucht :)

---

Das ist ja eine Behauptung mit drei Variablen:

k , m ,n .

Da müsste man wohl 3 mal vollst. Induktion machen.

Hier Induktion über n, weil das ja die Anzahl der

Summanden bestimmt.

In meiner Version hatte ich ja angenommen:

Es gibt ein n, bei dem es für alle  k und m gilt.

---

ist jetzt vielleicht eine dumme frage, aber ist es nicht so, dass bei m der Induktionsanfang gar nicht funktioniert?

Nehmen wir mal an n=0, dann kommt, wenn ich dass in meine Induktionsvoraussetzung einsetze, nicht das gleiche für die Induktion mit m heraus, oder?

---

Dann hast du doch

$$\sum \limits_{l=0}^{0}\begin{pmatrix} 0\\l \end{pmatrix}*\begin{pmatrix} m\\k \end{pmatrix}$$

Also nur einen Summanden

$$\begin{pmatrix} 0\\0 \end{pmatrix}*\begin{pmatrix} m\\k \end{pmatrix}$$

und das passt doch.

---

du hast volkommen recht. Ich habe es jetzt soweit verstanden (auh wenn man das warschienlich kaum gluaben kann) aber vielen Dank, dass du mir auch noch auf so eine blöde Frage geantwortet hast.

---

Hallo, ich bin über dieselbe Aufgabe gestolpert.

Unzwar habe ich nicht ganz verstanden, warum du über n summierst und nicht über k.

k kann doch kleiner als n sein und so ist das Ergebnis falsch?

Answer 2

Hallo

das willst du beweisen? Dann schreib es bitte auch hin .

$${\displaystyle {m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}}$$

die Induktion sollte über r laufen bei dir also k, m,n  beliebig

Gruß lul