TU Wien:Diskrete Mathematik für Informatik UE (Drmota)/Übungen WS10/Beispiel 9

Beweis von $s_{n,2}=(n-1)!H_{n-1}$ für $(n\ge 2)$ mittels vollständiger Induktion.

Induktionsanfang: $n=2$ ergibt trivialerweise $1=1$.

Induktionsvoraussetzung: Wir nehmen an, dass $s_{n,2}=(n-1)!H_{n-1}$ für alle $n>2$.

Induktionsbehauptung: Wir wollen zeigen, dass dann $s_{n+1,2}=n!H_n$.

Dazu gehen wir von der rekursiven Definition der Stirlingzahlen 1. Art aus: $s_{n,k}=s_{n-1,k-1}+(n-1)s_{n-1,k}$

Das bedeutet in unserem Fall: $s_{n+1,2}=s_{n,1}+n{s}_{n,2}$

Aus der VO wissen wir, dass $s_{n,1}=(n-1)!$ ist. D.h. durch Verwendung der Induktionsvoraussetzung erhalten wir: $s_{n+1,2}=(n-1)!+n(n-1)!H_{n-1}=n!(\frac{1}{n}+H_{n-1})=n!H_n$

QED