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\geq 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}+ns_{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