Stirling Zahlen Induktion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 00:11 Di 08.02.2011 | | Autor: | hilado |
| Aufgabe | Wenn man das Stirlingdreieck zweiter Art mit dem Pascal'schen Dreieck vergleicht, stellt man fest, dass die Stirlingzahlen "meistens" größer sind. Zeigen Sie, dass für m >= k >= 2 gilt:
[mm] S_{m, k} [/mm] >= [mm] \vektor{m \\ k}
[/mm]
Hinweis. Benutzen Sie eine doppelte Induktion nach m und k mit Induktionsanfang k = 2. Gehen Sie dabei folgendermaßen vor:
1. Für m >= 2 gilt [mm] S_{m, 2} [/mm] >= [mm] \vektor{m \\ 2}
[/mm]
2. Sei k >= 2 so, dass für alle m >= k gilt: [mm] S_{m, k} [/mm] >= [mm] \vektor{m \\ k}
[/mm]
Dann gilt für alle m' >= k + 1 auch: [mm] S_{m', k + 1} [/mm] >= [mm] \vektor{m' \\ k + 1}
[/mm]
Alternativ kann man sich überlegen, ob man das auch kombinatorisch beweisen kann. |
Also ich hab mal angefangen:
1)
Induktionsanfang: m = 2
[mm] S_{m, k} [/mm] = [mm] \summe_{j=0}^{k} (-1)^{k-j} \bruch{j^{m}}{j! (k - j)!}
[/mm]
[mm] S_{2, 2} [/mm] = 2.
[mm] \vektor{2 \\ 2} [/mm] = 1
Induktionsvorraussetzung:
[mm] S_{m, 2} [/mm] >= [mm] \vektor{m \\ 2}
[/mm]
zu zeigen:
[mm] S_{m + 1, 2} [/mm] >= [mm] \vektor{m + 1 \\ 2}
[/mm]
Induktionsschritt:
[mm] S_{m + 1, k + 1} [/mm] = [mm] S_{m, k} [/mm] + (k + 1) * [mm] S_{m, k + 1}
[/mm]
so hätte ich jetzt weiter gemacht, aber der zweite Summand bereitet mir irgendwie Kopfschmerzen. Hat jemand von euch ne Ahnung wie man an diese Aufgabe rangeht? Oder besser ein Tipp ?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Do 10.02.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
