Binomialkoeffizient Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:03 So 10.11.2013 | | Autor: | Arkathor |
| Aufgabe | | Sei m [mm] \in \IN \cup [/mm] {0}. Beweisen Sie durch vollständige Induktion, dass für alle n [mm] \in \IN \cup [/mm] {0} gilt: [mm] \summe_{k=0}^{n} \vektor{m+k \\ k} [/mm] = [mm] \vektor{m+n+1 \\ n} [/mm] |
Hallo
Also ich bin etwas in dem Beweis hängen geblieben und bräuchte einen Tipp:
IA: [mm] \summe_{k=0}^{0} \vektor{m \\ k} =\vektor{m \\ 0} [/mm] = 1 = [mm] \vektor{m
+1 \\ 0}
[/mm]
IS: [mm] \summe_{k=0}^{n+1} \vektor{m+k\\ k} =\summe_{k=0}^{n} \vektor{m+k \\ k} [/mm] + [mm] \vektor{m+n+1 \\ n+1} [/mm] = [mm] \vektor{m+n+1 \\ n} [/mm] + [mm] \vektor{m+n+1 \\ n+1}= \bruch{(m+n+1)!}{n!(m+1)!}+\bruch{(m+n+1)!}{m!(n+1)!}=\bruch{(m+n+1)!(n+1)!+(m+n+1)!(m+1)!}{(n+1)!(m+1)!}=\bruch{(m+n+1)!((n+1)!+(m+1)!)}{(n+1)!(m+1)!}
[/mm]
Und weiter komme ich nicht voran, würde mich sehr über Tipp freuen.
|
|
| |
|
Es gilt die Identität
[mm]\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}[/mm]
Die Begründung dieser ist kombinatorisch: Eine Menge der Mächtigkeit $n+1$ lässt sich in Mengen zerlegen, die das Element $n+1$ beinhalten und die, die das Element $n+1$ nicht beinhalten.
Diese Identität kannst du im IS anwenden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:48 So 10.11.2013 | | Autor: | Arkathor |
[mm] \bruch{(m+n+1)!}{n!(m+1)!}+\bruch{(m+n)!}{n!m!}+\bruch{(m+n)!}{(n+1)!(m+1)!}=\bruch{(m+n+1)!(n+1)+(m+n)!(m+1)(n+1)+(m+n)!}{(n+1)!(m+1)!}
[/mm]
Also dazu bin ich gekommen und wieder komme ich nicht wirklich weiter. Also ich denke irgendwo irgendwann muss ich etwas kurzen, aber wo und wann weis ich nicht.
|
|
|
| |
|
Genügt dir die kombinatorische Begründung nicht?
Dann doch nicht so kompliziert:
[mm]\binom{n}{k}+\binom{n}{k+1}=\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}=\ldots=\binom{n+1}{k+1}[/mm] (*)
Jetzt Haupnenner bilden, dann im Zähler [mm]n![/mm] ausklammern, fertig.
Überhaupt: Wenn du das als Übungsaufgabe abgeben musst, dann wäre dem Korrektor sicherlich geholfen, wenn du die verbliebene Aussage (*) als ein Lemma aufschreibst und es extra beweist.
|
|
|
|
