Binomialkoeff., Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:12 So 18.10.2009 | | Autor: | ChopSuey |
| Aufgabe | Zeige mittels vollst. Induktion, dass für alle $ n,k,m [mm] \in \mathbb [/mm] N $ die folgende Aussage gilt:
$ [mm] \ {n+m \choose k} [/mm] = [mm] \sum\limits_{i=0}^k [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k-i} $ |
Hallo,
das ist eine Hausübung, bei der ich so langsam alles, was mir so einfiel, probiert hab doch entweder ich habe gleich zu Beginn irgendwas falsch gemacht, oder ich seh etwas ganz wesentliches nicht.
Induktionsanfang: $ k = 0 [mm] $\\
[/mm]
$ {n+m [mm] \choose [/mm] 0} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] 0} [mm] $\\
[/mm]
$ 1 = 1*1 $ ist wahr. [mm] \\
[/mm]
Wir vermuten, die Aussage gilt für alle $ k [mm] \in \mathbb [/mm] N$.
Induktionsschritt: $k [mm] \to [/mm] k+1$
Es ist $ [mm] \sum\limits_{i=0}^k [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k-1}+...+{n [mm] \choose [/mm] k} {m [mm] \choose [/mm] 0} [mm] $\\
[/mm]
$ [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} = [mm] \sum\limits_{i=0}^k [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k-i} + {n [mm] \choose [/mm] k+1} {m [mm] \choose [/mm] 0} [mm] $\\
[/mm]
Folglich ist
$ [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} = {n [mm] \choose [/mm] 0} {m [mm] \choose [/mm] k}+{n [mm] \choose [/mm] 1} {m [mm] \choose [/mm] k-1}+...+{n [mm] \choose [/mm] k} {m [mm] \choose [/mm] 1} + {n [mm] \choose [/mm] k+1} {m [mm] \choose 0}$\\
[/mm]
$ {n+m [mm] \choose [/mm] k}+ {n [mm] \choose [/mm] k+1} {m [mm] \choose [/mm] 0} = [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} [mm] $\\
[/mm]
$ {n+m [mm] \choose [/mm] k}+ {n [mm] \choose [/mm] k+1} = [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} [mm] $\\
[/mm]
$ [mm] \frac{(n+m)!}{k!(n+m-k)!} [/mm] + [mm] \frac{n!}{(k+1)!(n-(k+1))!} [/mm] = [mm] \sum\limits_{i=0}^{k+1} [/mm] {n [mm] \choose [/mm] i} {m [mm] \choose [/mm] k+1-i} [mm] $\\
[/mm]
Ja, und alles, was danach kommt, sind bloß Versuche, die Brüche irgendwie so umzuformen, dass ich das Ganze auf den Ausdruck
$\ [mm] \vektor{n+m \\ k+1} [/mm] $ zurueckführen kann.
Würde mich freuen, wenn mir jemand sagen kann, ob ich etwas falsch gemacht habe und möglicherweise auch was genau. Vielleicht hab ich auch bloß nen Fehler in meinen Überlegungen.
Falls das bisher allerdings stimmt, reicht es, wenn ich weiss, dass ich mir bisschen mehr einfallen lassen muss.
Danke
Grüße
ChopSuey
|
|
| |
|
> Zeige mittels vollst. Induktion, dass für alle [mm]n,k,m \in \mathbb N[/mm]
> die folgende Aussage gilt:
>
> [mm]\ {n+m \choose k} = \sum\limits_{i=0}^k {n \choose i} {m \choose k-i}[/mm]
>
> Hallo,
>
> das ist eine Hausübung, bei der ich so langsam alles, was
> mir so einfiel, probiert hab doch entweder ich habe gleich
> zu Beginn irgendwas falsch gemacht, oder ich seh etwas ganz
> wesentliches nicht.
>
> Induktionsanfang: [mm]k = 0[/mm][mm] \\[/mm]
>
> [mm] {n+m \choose 0} = {n \choose 0} {m \choose 0}[/mm][mm] \\[/mm]
>
> [mm]1 = 1*1[/mm] ist wahr. [mm]\\[/mm]
>
> Wir vermuten nehmen an, die Aussage gilt für alle [mm]k \in \mathbb N[/mm].
>
> Induktionsschritt: [mm]k \to k+1[/mm]
>
>
> Es ist [mm]\sum\limits_{i=0}^k {n \choose i} {m \choose k-i} = {n \choose 0} {m \choose k}+{n \choose 1} {m \choose k-1}+...+{n \choose k} {m \choose 0}[/mm][mm] \\[/mm]
>
> [mm]\sum\limits_{i=0}^{k+1} {n \choose i} {m \choose k+1-i} = \sum\limits_{i=0}^k {n \choose i} {m \choose k-i} + {n \choose k+1} {m \choose 0}[/mm][mm] \\[/mm]
Hallo,,
das stimmt nicht.
Es ist
[mm]\sum\limits_{i=0}^{k+1} {n \choose i} {m \choose k+1-i} = \sum\limits_{i=0}^k {n \choose i} {m \choose k+1-i} + {n \choose k+1} {m \choose 0}[/mm][mm] \\[/mm]
Gruß v. Angela
>
> Folglich ist
>
> [mm]\sum\limits_{i=0}^{k+1} {n \choose i} {m \choose k+1-i} = {n \choose 0} {m \choose k}+{n \choose 1} {m \choose k-1}+...+{n \choose k} {m \choose 1} + {n \choose k+1} {m \choose 0}[/mm][mm] \\[/mm]
>
> [mm]{n+m \choose k}+ {n \choose k+1} {m \choose 0} = \sum\limits_{i=0}^{k+1} {n \choose i} {m \choose k+1-i}[/mm][mm] \\[/mm]
>
> [mm]{n+m \choose k}+ {n \choose k+1} = \sum\limits_{i=0}^{k+1} {n \choose i} {m \choose k+1-i}[/mm][mm] \\[/mm]
>
> [mm]\frac{(n+m)!}{k!(n+m-k)!} + \frac{n!}{(k+1)!(n-(k+1))!} = \sum\limits_{i=0}^{k+1} {n \choose i} {m \choose k+1-i}[/mm][mm] \\[/mm]
>
> Ja, und alles, was danach kommt, sind bloß Versuche, die
> Brüche irgendwie so umzuformen, dass ich das Ganze auf den
> Ausdruck
>
> [mm]\ \vektor{n+m \\ k+1}[/mm] zurueckführen kann.
>
> Würde mich freuen, wenn mir jemand sagen kann, ob ich
> etwas falsch gemacht habe und möglicherweise auch was
> genau. Vielleicht hab ich auch bloß nen Fehler in meinen
> Überlegungen.
> Falls das bisher allerdings stimmt, reicht es, wenn ich
> weiss, dass ich mir bisschen mehr einfallen lassen muss.
>
> Danke
> Grüße
> ChopSuey
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:18 So 18.10.2009 | | Autor: | ChopSuey |
Hallo Angela,
diese blöde obere Grenze 
Vielen Dank
Grüße
ChopSuey
|
|
|
|
