Vandermonde Identität < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:35 Sa 30.04.2011 | | Autor: | dlns |
Hallo Forum.
Ich hab hier einen Beweis zur Vandermonde-Identität gefunden, den ich nicht so ganz verstehe: http://www.proofwiki.org/wiki/Chu-Vandermonde_Identity
Bis zum dritten Schritt ist das noch in Ordnung, aber wieso wird im vierten Umformungsschritt aus dem m ein (n-k)?
Viele Grüße
D.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:47 So 01.05.2011 | | Autor: | felixf |
Moin,
> Ich hab hier einen Beweis zur Vandermonde-Identität
> gefunden, den ich nicht so ganz verstehe:
> http://www.proofwiki.org/wiki/Chu-Vandermonde_Identity
>
> Bis zum dritten Schritt ist das noch in Ordnung, aber wieso
> wird im vierten Umformungsschritt aus dem m ein (n-k)?
jedes $m [mm] \in \IN$ [/mm] laesst sich eindeutig als $n - k$ darstellen, wenn man $k$ festhaelt und $n [mm] \in \IN$ [/mm] frei waehlen kann.
Deswegen wird in der Zeile $m$ ueberall durch $n - k$ ersetzt, da es nur innerhalb der Summe ueber $k$ vorkommt (und in jedem Summand ist das $k$ fest). Das ganze ist nicht so schoen aufgeschrieben, da es eigentlich eine Summe ueber $n$ werden sollte (genauer: aus [mm] $\sum_{m=0}^{...} [/mm] f(m)$ wird [mm] $\sum_{n=k}^{...+k} [/mm] f(n - k)$).
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:22 So 01.05.2011 | | Autor: | dlns |
Hallo Felix.
Erstmal danke für die Antwort, das hat mir schon etwas weiter geholfen. Ich hab die Schritte jetzt so weit:
[mm]
\sum_{i=0}^{r+s} {r+s \choose i} x^i
& = (1+x)^{r+s} = (1+x)^r(1+x)^s \\
& = \sum_{j=0}^r {r \choose j} x^j \sum_{i=0}^s {s \choose i} x^i
= \sum_{j=0}^r \left[{r \choose j} x^j \sum_{i=0}^s {s \choose i} x^i\right] \\
& = \sum_{j=0}^r \left[{r \choose j} x^j \sum_{i=j}^{s+j} {s \choose i-j} x^{i-j}\right] \\
& = \sum_{j=0}^r \sum_{i=j}^{s+j} {r \choose j} {s \choose i-j} x^{i}.
[/mm]
Aber von hier aus komm ich jetzt nicht mehr so richtig weiter. Die innere Summe hat ja bis dahin falsche Grenzen. Wie kann ich die entsprechend anpassen? Für die untere Grenze hätte ich jetzt angenommen, dass ${n [mm] \choose [/mm] k} = 0$ für $k < 0$ ist, aber was mach ich mit der oberen Grenze $s+j$? Und wie krieg ich das [mm] $x^i$ [/mm] aus der inneren Summe in die äußere (also [mm] $x^j$), [/mm] damit die innere Summe zum Koeffizienten wird?
Viele Grüße
D.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:09 So 01.05.2011 | | Autor: | felixf |
Moin D.!
> Erstmal danke für die Antwort, das hat mir schon etwas
> weiter geholfen. Ich hab die Schritte jetzt so weit:
> [mm]
\sum_{i=0}^{r+s} {r+s \choose i} x^i
& = (1+x)^{r+s} = (1+x)^r(1+x)^s \\
& = \sum_{j=0}^r {r \choose j} x^j \sum_{i=0}^s {s \choose i} x^i
= \sum_{j=0}^r \left[{r \choose j} x^j \sum_{i=0}^s {s \choose i} x^i\right] \\
& = \sum_{j=0}^r \left[{r \choose j} x^j \sum_{i=j}^{s+j} {s \choose i-j} x^{i-j}\right] \\
& = \sum_{j=0}^r \sum_{i=j}^{s+j} {r \choose j} {s \choose i-j} x^{i}.
[/mm]
>
> Aber von hier aus komm ich jetzt nicht mehr so richtig
> weiter. Die innere Summe hat ja bis dahin falsche Grenzen.
> Wie kann ich die entsprechend anpassen? Für die untere
Du musst die Summen umparametrisieren. Du willst ja aussen eine Summe ueber $i$ stehen haben im Ergebnis.
Also. Momentan summierst du ueber alle Paare $(i, j)$ mit $0 [mm] \le [/mm] j [mm] \le [/mm] r$ und $j [mm] \le [/mm] i [mm] \le [/mm] s + j$.
Erstmal: wenn $j > r$ oder $i > s + j$ ist, dann ist [mm] $\binom{r}{j} \binom{s}{i - j} [/mm] = 0$. Also kannst du genausogut ueber die (unendlich vielen) Paare $(i, j)$ mit $0 [mm] \le [/mm] j$ und $j [mm] \le [/mm] i$, also mit $0 [mm] \le [/mm] j [mm] \le [/mm] i$ summieren.
Anstelle [mm] $\sum_{j=0}^\infty \sum_{i=j}^\infty$ [/mm] kannst du also [mm] $\underset{0 \le j \le i}{\sum\sum}$ [/mm] oder gleich [mm] $\sum_{i=0}^\infty \sum_{j=0}^i$ [/mm] schreiben.
Damit ist die obige Summe gleich [mm] $\sum_{i=0}^\infty \sum_{j=0}^i \binom{r}{j} \binom{s}{i - j} x^i$. [/mm] Und da der Summand fuer $i > r + s$ eh gleich 0 ist, kannst du die erste Summe auch bis $r + s$ gehen lassen (anstelle [mm] $\infty$).
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:39 So 01.05.2011 | | Autor: | dlns |
Hallo Felix.
Nochmal danke. Das Umparametrisieren von Doppelsummen finde ich (allgemein) ziemlich unübersichtlich. Aber so grob hab ich's verstanden.
Viele Grüße
D.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:55 So 01.05.2011 | | Autor: | felixf |
Moin D.!
> Nochmal danke. Das Umparametrisieren von Doppelsummen finde
> ich (allgemein) ziemlich unübersichtlich.
Es ist auch immer etwas muehsam :)
Ich find es hilft sehr, wenn man den Zwischenschritt (hier: $0 [mm] \le [/mm] j [mm] \le [/mm] i$) hinschreibt: von dem kommt man sofort zu beiden Parametrisierungen [mm] $\sum_{j=0}^\infty \sum_{i=j}^\infty$ [/mm] und [mm] $\sum_{i=0}^\infty \sum_{j=0}^i$.
[/mm]
LG Felix
|
|
|
|
