kombinatorisches Lemma(Summen über Binomialkoeffizienten) beweisen

08.01.2012, 16:12	acki_	Auf diesen Beitrag antworten »
kombinatorisches Lemma(Summen über Binomialkoeffizienten) beweisen Hallo! Ich versuche momentan folgenden Satz zu beweisen: Für ganze Zahlen u,v >= 0 und w>=1 gilt: $\begin{eqnarray} \sum_{r=1}^{v} \binom{r}{w} \binom{u+v-r}{u} = \binom{u+v+1}{u+w+1} \end{eqnarray}$ Ich habe eine Induktion über v versucht, aber das Ding wehrt sich. Der Induktionsschritt sähe ja so aus: $\begin{eqnarray} \sum_{r=1}^{v+1} \binom{r}{w} \binom{u+v+1-r}{u} = \binom{u+v+1+1}{u+w+1} \end{eqnarray}$ Ich versuche dann immer die Summe für v+1 (linke Seite) so umzuformen, dass ich die IV einsetzen kann und dass möglichst was rauskommt, was der rechten Seite für v+1 ähnelt..... Das mache ich, indem ich mit Hilfe von $\begin{eqnarray} \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \end{eqnarray}$ den rechten Binomialkoeffizienten umforme: $\begin{eqnarray} \binom{u+v+1-r}{u}=\binom{u+v+1-r-1}{u-1}+ \binom{u+v+1-r-1}{u} \end{eqnarray}$ Es entstehen zwei Summen, die ich außeinanderreiße und einzeln betrachte, ungefähr so: $\begin{eqnarray} \sum_{r=1}^{v+1} \binom{r}{w} \binom{u+v-r}{u-1} + \sum_{r=1}^{v+1} \binom{r}{w} \binom{u+v-r}{u} \end{eqnarray}$ Die rechte der beiden Summen erlaubt mir, die IV einzusetzen, nachdem ich den v+1 Summand abgelöst habe. Die andere Summe könnte man vielleicht umwandeln mit der IV für u'=u+1 (die IV gilt zwar nur für ein festes v, aber für beliebige u...). Das schlägt jedoch fehl.....Was man aber stattdessen einsetzen könnte wäre die Summe für u-1 und v+1, was man meines Erachtens natürlich nicht darf, weil der Fall von v+1 ja genau zu beweisen ist und nicht zur Induktionsvoraussetzung gehört. Komischerweise schlägt meine Literatur (U. Krengel, Einf. i.d. WK'-Theorie, S122) genau das vor?!? Warum sollte ich sowas dürfen? In Wortlaut des Buches ist der Beweis so skizziert: "Die Fälle für u=0 (v,w beliebig, v=0 (u,w beliebig), w>=v und v=1 sind leicht direkt nachzurechnen. Dann verwendet man beim Schluss von v auf v+1 bei gegebenem u die Aussage für u und v und die Aussage für u-1 und v+1." Vielleicht blickt da ja jemand von Euch durch oder es besteht nur ein Missverständnis bei mir, wie ich das mit der Induktion angehen sollte oder was ich alles darf... Oder es gibt vielleicht einen viel leichteren Weg.... VIEEELEN DANK!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »