noch eine Induktion < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:02 Mo 25.07.2005 | | Autor: | Bastiane |
Hallo!
Leider habe ich hier noch eine Induktion, wo ich noch weniger hinbekomme. :-(
Für eine reelle Zahl x und eine natürliche Zahl k werde definiert
[mm] \vektor{ x \\ k } [/mm] = [mm] \produkt_{j=1}^{k} \bruch{x-j+1}{j}.
[/mm]
Man beweise
[mm] \vektor{ x+y \\ n } [/mm] = [mm] \summe_{k=0}^n \vektor{x \\ n-k}\vektor{y\\k}
[/mm]
Den Induktionsanfang für n=0 habe ich, aber dann geht irgendwie überhaupt nichts mehr. Hat jemand einen Ansatz für mich? Würde mich freuen.
Viele Grüße
Bastiane
![[banane]](/images/smileys/banane.gif "[banane]")
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:04 Mo 25.07.2005 | | Autor: | Hanno |
Hallo Christiane.
Für natürliche $x,y$ lässt sich die Behauptung kombinatorisch beweisen. Sei eine Menge von $x+y$ Objekten, $x$ Objekten von Typ A, $y$ Objekten von Typ B, gegeben. Gezählt werden sollen die Möglichkeiten, eine Auswahl von $n$ Objekten aus dieser Menge zu treffen. Diese Anzahl entspricht [mm] $\vektor{x+y\\ n}$. [/mm] Unterscheiden wir die Auswahlen bezüglich der Anzahl der in ihnen enthaltenen Objekte von Typ A, so ergibt sich folgendes: sollen in der Auswahl $k$ Objekte von Typ A enthalten sein, so sind $k$ der $x$ Objekte des Typs A und $n-k$ der $y$ Objekte des Typs $B$ auszuwählen, wofür es [mm] $\vektor{x\\ k}\vektor{y\\ n-k}$ [/mm] Möglichkeiten gibt. Jede Auswahl besitzt eine eindeutig bestimmte Anzahl an Objekten des Typs A und des Typs B, die jeweils zwischen 0 und n liegen und sich zu $n$ ergänzen; die Gesamtanzahl der Auswahlen kann also durch Summation von [mm] $\vektor{x\\ k}\vektor{y\\ n-k}$ [/mm] für $k=0,1,...,n$ erhalten werden, wobei allerdings vorausgesetzt werden muss, dass [mm] $x,y\geq [/mm] n$ ist. Man erhält somit:
[mm] $\vektor{x+y\\ n}=\summe_{k=0}^{n} \vektor{x\\ k}\vektor{y\\ n-k}$.
[/mm]
Dies ist die sog. Vandermondsche Identität.
Für reelle $x,y$ lässt sich diese Argumentation nicht durchführen bzw. mir ist eine solche kombinatorische Interpretation nicht bekannt.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:48 Mo 25.07.2005 | | Autor: | SEcki |
> Für reelle [mm]x,y[/mm] lässt sich diese Argumentation nicht
> durchführen bzw. mir ist eine solche kombinatorische
> Interpretation nicht bekannt.
Daruas lässt sie sich aber herleiten! Vgl. dazu Kömigsberger, Ana I, Kapitel 4.2, Seite 54: hier betrachtet man jeweils [m](1+t)^{x+y}=(1+t)^x(1+t)^y[/m], nimmt als Polynome in t und beweist das mit dem Identitätssatz für Polynome, da das ganze für alle antürlichen Zahlen schon gilt.
Aber einen reinen Beeis mit Induktion wäre schön.
SEcki
|
|
|
| |
|
Hallo Bastiane,
Ich habe in meinem Kombinatorik-Skriptum einen Beweis dieser Identität gefunden, der die Theorie der hypergeometrischen Reihen und insbesondere die Kummer-Identität benutzt.
Unglücklicherweise steht als "Beweis" dieser Identität nur das eine Wort "Computeralgebra" in meinem Skriptum.
Außerdem habe ich den Rest des Beweises auch noch nicht ganz durchschaut. Es wären allerdings nur ein paar Zeilen.
Ich möchte trotzdem vorher von Dir wissen, ob ihr hg. Reihen, und die Kummer-Identität behandelt habt, oder ob Dir auch so mit dieser Antwort geholfen wäre.
Liebe Grüße,
Holy Diver
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:52 Di 26.07.2005 | | Autor: | Bastiane |
Hallo ihr Drei!
Danke für eure Antworten. Danke Hanno, für deine schöne Erklärung, die kann ich sogar nachvollziehen!  Allerdings ist der Binomialkoeffizient für natürliche Zahlen n und k genauso definiert, und daraus folgt dann die (jedenfalls mir) besser bekannte "Definition" [mm] \vektor{n\\k}=\bruch{n!}{k!(n-k)!} [/mm] - vgl. Otto Forster, Analysis I (die Seitenzahl und so lasse ich mal lieber weg, da ich hier eine uralte Ausgabe habe  ). Demnach ist bei dieser Aufgabe dann wohl gemeint, dass x nicht natürlich ist, und es steht ja auch dabei, dass x reell sein soll.
Was im Königsberger dazu steht, kann ich im Moment nicht nachvollziehen, da ich hier nur den zweiten habe. :-( Werde mir den ersten aber mal besorgen und nachgucken.
Und an Holy Diver: Lass mal gut sein mit dem Beweis, mit deinen Begriffen kann ich nichts anfangen, und da die Aufgabe in einem Kapitel über vollständige Induktion steht, denke ich, dass die auch solch einen Beweis haben wollen. Allerdings muss ich ja nicht jede Aufgabe können.
Ich lasse die Frage mal auf unbeantwortet, vielleicht fällt ja doch irgendwem noch ein Beweis mit Induktion ein.
Aber vielen Dank für eure Mühen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:21 Mi 27.07.2005 | | Autor: | Stefan |
Liebe Christiane!
Den Induktionsschritt kann man so führen:
${{x+y} [mm] \choose [/mm] {n+1}}$
$= [mm] \prod\limits_{j=1}^{n+1} \frac{x+y+j-1}{(n+1)!}$
[/mm]
$= [mm] \prod\limits_{j=1}^n \frac{x+y+j-1}{n!} \cdot \frac{x+y-n}{n+1}$
[/mm]
$= [mm] \frac{x+y-n}{n+1} \cdot [/mm] {{x+y} [mm] \choose [/mm] n}$
[mm] $\stackrel{(IV)}{=} \frac{x+y-n}{n+1} \cdot \sum\limits_{k=0}^n [/mm] {x [mm] \choose{n- k}} \cdot [/mm] {y [mm] \choose [/mm] k}$
[mm] $=\frac{1}{n+1} \sum\limits_{k=0}^n \frac{x+y-n}{n+1} \cdot \prod\limits_{i=1}^{n-k} \frac{x-i+1}{i!} \cdot \prod\limits_{j=1}^k \frac{y-j+1}{j!}$
[/mm]
$= [mm] \frac{1}{n+1} \sum\limits_{k=0}^n \frac{(x-n+k) + (y-k)}{n+1} \cdot \prod\limits_{i=1}^{n-k} \frac{x-i+1}{i!} \cdot \prod\limits_{j=1}^k \frac{y-j+1}{j!}$
[/mm]
$= [mm] \frac{1}{n+1} \cdot \left[\sum\limits_{k=0}^n (n-k+1) \cdot \prod\limits_{i=1}^{n-k+1} \frac{x-i+1}{i!} \cdot \prod\limits_{j=1}^k \frac{y-j+1}{j!} + \sum\limits_{k=0}^n (k+1) \cdot \prod\limits_{i=1}^{n-k} \frac{x-i+1}{i!} \cdot \prod\limits_{j=1}^{k+1} \frac{y-j+1}{j!} \right]$
[/mm]
$= [mm] \frac{1}{n+1} \cdot \left[\sum\limits_{k=0}^n (n-k+1) \cdot {x \choose {n-k+1}} \cdot {y \choose k} + \sum\limits_{k=0}^n (k+1) \cdot{x \choose {n-k}} \cdot {y \choose {k+1}} \right]$
[/mm]
$= [mm] \frac{1}{n+1} \cdot \left[(n+1) \cdot {x \choose {n+1}} + \sum\limits_{k=1}^n (n-k+1) \cdot {x \choose {n-k+1}} \cdot {y \choose k} + \sum\limits_{k=0}^{n-1} (k+1) {x \choose {n-k}} \cdot {y \choose {k+1}} + (n+1) \cdot {y \choose {n+1}} \right]$
[/mm]
$= [mm] \frac{1}{n+1} \cdot \left[(n+1) \cdot {x \choose {n+1}} + \sum\limits_{k=1}^n (n-k+1) \cdot {x \choose {n-k+1}} \cdot {y \choose k} + \sum\limits_{k=1}^{n} k \cdot {x \choose {n-k+1}} \cdot {y \choose k} + (n+1) \cdot {y \choose {n+1}} \right]$
[/mm]
$= {x [mm] \choose [/mm] {n+1}} + [mm] \frac{1}{n+1} \cdot \sum\limits_{k=1}^n [/mm] (n+1) [mm] \cdot [/mm] {x [mm] \choose [/mm] {n-k+1}} [mm] \cdot [/mm] {y [mm] \choose [/mm] k} + {y [mm] \choose [/mm] {n+1}} $
$= [mm] \sum\limits_{k=0}^{n+1} [/mm] {x [mm] \choose [/mm] {n+1-k}} [mm] \cdot [/mm] {y [mm] \choose [/mm] k}$.
Liebe Grüße
Stefan
|
|
|
|
