Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:55 Do 05.12.2013 | | Autor: | ne1 |
| Aufgabe | Für $x [mm] \in \mathbb{R},\ [/mm] k [mm] \in \mathbb{N}$ [/mm] definiert man ${x [mm] \choose [/mm] k} := [mm] \prod_{j=1}^{k} \frac{x-j+1}{j} [/mm] = [mm] \frac{x(x-1) \cdot ...\cdot (x-k+1)}{k!}$, [/mm] insbesondere ${x [mm] \choose [/mm] 0} = 1$.
Beweise ${x + y [mm] \choose [/mm] n} = [mm] \sum_{k=0}^{n} [/mm] {x [mm] \choose [/mm] n-k} {y [mm] \choose [/mm] k}$. |
Beweis: Mithilfe der VI nach $n$.
IA: $n=0$ habe ich bereits bewiesen.
IS $n [mm] \rightarrow [/mm] n+1$:
Annahme: ${x + y [mm] \choose [/mm] n} = [mm] \sum_{k=0}^{n} [/mm] {x [mm] \choose [/mm] n-k} {y [mm] \choose [/mm] k}$.
Man muss zeigen: ${x + y [mm] \choose [/mm] n+1} = [mm] \sum_{k=0}^{n+1} [/mm] {x [mm] \choose [/mm] n+1-k} {y [mm] \choose [/mm] k}$.
[mm] $\sum_{k=0}^{n+1} [/mm] {x [mm] \choose [/mm] n+1-k} {y [mm] \choose [/mm] k} = [mm] \sum_{k=0}^{n} [/mm] {x [mm] \choose [/mm] n+1-k} {y [mm] \choose [/mm] k} + {x [mm] \choose [/mm] n+1-(n+1)}{y [mm] \choose [/mm] n+1} = [mm] \sum_{k=0}^{n} [/mm] {x [mm] \choose [/mm] n+1-k} {y [mm] \choose [/mm] k} + {y [mm] \choose [/mm] n+1}$.
Hier weiss ich nicht mehr weiter. Das $n+1$ stört mich in der Summe um IV zu nutzen. Ich habe geschafft die Summe zu zerlegen um statt $n+1-k$, $n-k$ zu bekommen, aber dann entsteht eine neue Summe und bin deshalb bisschen verzweifelt. Von der anderen Seite also ${x + y [mm] \choose [/mm] n+1}$ bin ich auch nicht weit gekommen. Ich konnte die IV anwenden, aber dann ist ein Produkt entstanden wo ich nicht weiter gekommen bin. Deshalb bitte ich um Tipps.
Danke im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:48 Do 05.12.2013 | | Autor: | DieAcht |
Hallo,
> Für [mm]x \in \mathbb{R},\ k \in \mathbb{N}[/mm] definiert man [mm]{x \choose k} := \prod_{j=1}^{k} \frac{x-j+1}{j} = \frac{x(x-1) \cdot ...\cdot (x-k+1)}{k!}[/mm],
> insbesondere [mm]{x \choose 0} = 1[/mm].
>
> Beweise [mm]{x + y \choose n} = \sum_{k=0}^{n} {x \choose n-k} {y \choose k}[/mm].
>
>
> Beweis: Mithilfe der VI nach [mm]n[/mm].
>
> IA: [mm]n=0[/mm] habe ich bereits bewiesen.
>
> IS [mm]n \rightarrow n+1[/mm]:
> Annahme: [mm]{x + y \choose n} = \sum_{k=0}^{n} {x \choose n-k} {y \choose k}[/mm].
>
> Man muss zeigen: [mm]{x + y \choose n+1} = \sum_{k=0}^{n+1} {x \choose n+1-k} {y \choose k}[/mm].
>
> [mm]\sum_{k=0}^{n+1} {x \choose n+1-k} {y \choose k} = \sum_{k=0}^{n} {x \choose n+1-k} {y \choose k} + {x \choose n+1-(n+1)}{y \choose n+1} = \sum_{k=0}^{n} {x \choose n+1-k} {y \choose k} + {y \choose n+1}[/mm].
>
> Hier weiss ich nicht mehr weiter. Das [mm]n+1[/mm] stört mich in
> der Summe um IV zu nutzen. Ich habe geschafft die Summe zu
> zerlegen um statt [mm]n+1-k[/mm], [mm]n-k[/mm] zu bekommen, aber dann
> entsteht eine neue Summe und bin deshalb bisschen
> verzweifelt.
Dann müsstest du doch einen Faktor haben, den du vor die Summe schreiben kannst.
[mm] \summe_{k=0}^{n}\vektor{x \\ n+1-k}\vektor{y \\ k}+\vektor{y \\ n+1}=\summe_{k=0}^{n}\alpha\vektor{x \\ n-k}\vektor{y \\ k}+\vektor{y \\ n+1}=\alpha(\summe_{k=0}^{n}\vektor{x \\ n-k}\vektor{y \\ k})+\vektor{y \\ n+1}
[/mm]
mit [mm] \alpha=\ldots
[/mm]
Dann weiter mit der Induktionsvorraussetzung.
Ich bin mir aber ziemlich sicher, dass du das direkt beweisen kannst über den gegebenen Tipp. Schreibe doch mal die Summe aus. Da sollte sich einiges kürzen lassen.
> Von der anderen Seite also [mm]{x + y \choose n+1}[/mm]
> bin ich auch nicht weit gekommen. Ich konnte die IV
> anwenden, aber dann ist ein Produkt entstanden wo ich nicht
> weiter gekommen bin. Deshalb bitte ich um Tipps.
>
> Danke im Voraus.
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:45 Fr 06.12.2013 | | Autor: | ne1 |
Danke für Deine Hilfe.
${x [mm] \choose [/mm] n+1-k} = [mm] \prod_{j=1}^{n-k} \frac{x-j+1}{j} \cdot \frac{x-n+k}{n+1-k} [/mm] = {x [mm] \choose [/mm] n-k} [mm] \cdot \frac{x-n+k}{n+1-k}$
[/mm]
Ich habe also:
[mm] $\sum_{k=0}^{n} [/mm] {x [mm] \choose [/mm] n+1-k} {y [mm] \choose [/mm] k} + {y [mm] \choose [/mm] n+1} = [mm] \sum_{k=0}^{n} [/mm] {x [mm] \choose [/mm] n-k}{y [mm] \choose k}\cdot \frac{x-n+k}{n+1-k} [/mm] + {y [mm] \choose [/mm] n+1}$.
Und nun? IV kann ich jetzt eigentlich nicht anwenden, da die Summe sich auch auf [mm] $\frac{x-n+k}{n+1-k}$ [/mm] bezieht. Ich kann es auch nicht vorziehen, weil es von $k$ abhängig ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:31 Fr 06.12.2013 | | Autor: | DieAcht |
> Danke für Deine Hilfe.
>
> [mm]{x \choose n+1-k} = \prod_{j=1}^{n-k} \frac{x-j+1}{j} \cdot \frac{x-n+k}{n+1-k} = {x \choose n-k} \cdot \frac{x-n+k}{n+1-k}[/mm]
Okay, das sehe ich nicht direkt. Mal sehen:
[mm] \vektor{x \\ n-k+1}:=\produkt_{j=1}^{n+1-k}\frac{x-j+1}{j}=\produkt_{j=1}^{n-k}\frac{x-j+1}{j}*\frac{x-(n-k+1)+1}{n-k+1}=\produkt_{j=1}^{n-k}\frac{x-j+1}{j}*\frac{x-n+k}{n-k+1}=\vektor{x \\ n-k}*\frac{x-n+k}{n-k+1}
[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
>
> Ich habe also:
> [mm]\sum_{k=0}^{n} {x \choose n+1-k} {y \choose k} + {y \choose n+1} = \sum_{k=0}^{n} {x \choose n-k}{y \choose k}\cdot \frac{x-n+k}{n+1-k} + {y \choose n+1}[/mm].
Okay, ich musste erstmal durchgucken was du meinst. Nächstes mal bitte weiter zitieren.
Zu zeigen war: [mm]{x + y \choose n} = \sum_{k=0}^{n} {x \choose n-k} {y \choose k}[/mm]
Wir waren bei [mm] n\longrightarrow [/mm] $n+1$:
[mm]\sum_{k=0}^{n+1} {x \choose n+1-k} {y \choose k} = \sum_{k=0}^{n} {x \choose n+1-k} {y \choose k} + {x \choose n+1-(n+1)}{y \choose n+1} = \sum_{k=0}^{n} {x \choose n+1-k} {y \choose k} + {y \choose n+1}[/mm]
>
> Und nun? IV kann ich jetzt eigentlich nicht anwenden, da
> die Summe sich auch auf [mm]\frac{x-n+k}{n+1-k}[/mm] bezieht. Ich
> kann es auch nicht vorziehen, weil es von [mm]k[/mm] abhängig ist.
Ja, du musst das ganze unabhängig von $k$ machen.
Wieso probierst du es nicht mit einem direkten Beweis?
Von rechts nach linkes!
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:41 Sa 07.12.2013 | | Autor: | ne1 |
> Wieso probierst du es nicht mit einem direkten Beweis?
>
> Von rechts nach linkes!
>
Was meinst du genau damit?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:16 Sa 07.12.2013 | | Autor: | abakus |
> > Wieso probierst du es nicht mit einem direkten Beweis?
> >
> > Von rechts nach linkes!
> >
> Was meinst du genau damit?
>
Hallo,
damit soll sicher gemeint sein: ohne Induktion.
Forme die rechte Seite so lange um, bis du die linke Seite erhältst.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:17 So 08.12.2013 | | Autor: | ne1 |
Bist Du Dir sicher, dass ohne Induktion die Aufgabe einfacher zu lösen ist?
linke Seite:
${ x + y [mm] \choose [/mm] n } = [mm] \prod_{j=1}^{n} \frac{x+y-j+1}{j} [/mm] = [mm] \frac{(x+y)(x+y-1)\cdot ... \cdot (x+y-n+1)}{n!}$
[/mm]
rechte Seite:
[mm] $\sum_{k=0}^{n} [/mm] {x [mm] \choose [/mm] n-k}{y [mm] \choose [/mm] k} = [mm] \sum_{k=0}^{n} (\prod_{j=1}^{n-k}\frac{x-j+1}{j})(\prod_{j=1}^{k}\frac{y-j+1}{j}) [/mm] = [mm] \sum_{k=0}^{n} \frac{x(x-1)\cdot ... \cdot (x-n+k+1)}{(n-k)!} \cdot \frac{y(y-1)\cdot ... \cdot (y-k+1)}{k!}$
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:34 So 08.12.2013 | | Autor: | ne1 |
Das war quatsch. Bitte löschen.
|
|
|
|
